K
- key typeT
- data typepublic class GenericFibonacciHeap<K,T> extends Object
Note that this implementation is not synchronized. If multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set.
Modifier and Type | Class and Description |
---|---|
class |
GenericFibonacciHeap.Node
The Fibonacci heap node.
|
Constructor and Description |
---|
GenericFibonacciHeap(Comparator<K> comparator)
Constructs an empty heap.
|
Modifier and Type | Method and Description |
---|---|
void |
clear()
Removes all elements from this heap.
|
GenericFibonacciHeap.Node |
insert(K key,
T data)
Inserts a new element into the heap.
|
boolean |
isEmpty()
Tests if the Fibonacci heap is empty or not.
|
GenericFibonacciHeap.Node |
min()
Returns the smallest element in the heap.
|
GenericFibonacciHeap.Node |
removeMin()
Removes the smallest element from the heap.
|
int |
size()
Returns the size of the heap which is measured in the number of elements contained in the
heap.
|
String |
toString()
Creates a String representation of this Fibonacci heap.
|
static <K,T> GenericFibonacciHeap<K,T> |
union(GenericFibonacciHeap<K,T> h1,
GenericFibonacciHeap<K,T> h2)
Joins two Fibonacci heaps into a new one.
|
public GenericFibonacciHeap(Comparator<K> comparator)
comparator
- the comparator for key comparisonspublic boolean isEmpty()
Running time: $O(1)$ actual
public void clear()
public GenericFibonacciHeap.Node insert(K key, T data)
Running time: O(1) actual
key
- the keydata
- the valuepublic GenericFibonacciHeap.Node min()
Running time: O(1) actual
public GenericFibonacciHeap.Node removeMin()
Running time: $O(\log n)$ amortized
public int size()
Running time: $O(1)$ actual
public static <K,T> GenericFibonacciHeap<K,T> union(GenericFibonacciHeap<K,T> h1, GenericFibonacciHeap<K,T> h2)
Running time: $O(1)$ actual
K
- type of key stored in the heapT
- type of data stored in the heaph1
- first heaph2
- second heapCopyright © 2018. All rights reserved.