java.lang.Object  
↳  es.usc.citius.lab.hipster.collections.FibonacciHeap<T> 
Author: Keith Schwarz ([email protected])
An implementation of a priority queue backed by a Fibonacci heap, as described by Fredman and Tarjan. Fibonacci heaps are interesting theoretically because they have asymptotically good runtime guarantees for many operations. In particular, insert, peek, and decreasekey all run in amortized O(1) time. dequeueMin and delete each run in amortized O(lg n) time. This allows algorithms that rely heavily on decreasekey to gain significant performance boosts. For example, Dijkstra's algorithm for singlesource shortest paths can be shown to run in O(m + n lg n) using a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial heap. Internally, a Fibonacci heap is represented as a circular, doublylinked list of trees obeying the minheap property. Each node stores pointers to its parent (if any) and some arbitrary child. Additionally, every node stores its degree (the number of children it has) and whether it is a "marked" node. Finally, each Fibonacci heap stores a pointer to the tree with the minimum value. To insert a node into a Fibonacci heap, a singleton tree is created and merged into the rest of the trees. The merge operation works by simply splicing together the doublylinked lists of the two trees, then updating the min pointer to be the smaller of the minima of the two heaps. Peeking at the smallest element can therefore be accomplished by just looking at the min element. All of these operations complete in O(1) time. The tricky operations are dequeueMin and decreaseKey. dequeueMin works by removing the root of the tree containing the smallest element, then merging its children with the topmost roots. Then, the roots are scanned and merged so that there is only one tree of each degree in the root list. This works by maintaining a dynamic array of trees, each initially null, pointing to the roots of trees of each dimension. The list is then scanned and this array is populated. Whenever a conflict is discovered, the appropriate trees are merged together until no more conflicts exist. The resulting trees are then put into the root list. A clever analysis using the potential method can be used to show that the amortized cost of this operation is O(lg n), see "Introduction to Algorithms, Second Edition" by Cormen, Rivest, Leiserson, and Stein for more details. The other hard operation is decreaseKey, which works as follows. First, we update the key of the node to be the new value. If this leaves the node smaller than its parent, we're done. Otherwise, we cut the node from its parent, add it as a root, and then mark its parent. If the parent was already marked, we cut that node as well, recursively mark its parent, and continue this process. This can be shown to run in O(1) amortized time using yet another clever potential function. Finally, given this function, we can implement delete by decreasing a key to \infty, then calling dequeueMin to extract it.Hipster author's note: This implementation was taken from http://www.keithschwarz.com/interesting/code/?dir=fibonacciheap
Nested Classes  

class  FibonacciHeap.Entry<T> 
Public Constructors  

FibonacciHeap() 
Public Methods  

void 
decreaseKey(Entry<T> entry, double newPriority)
Decreases the key of the specified element to the new priority.
 
void 
delete(Entry<T> entry)
Deletes this Entry from the Fibonacci heap that contains it.
 
Entry<T> 
dequeueMin()
Dequeues and returns the minimum element of the Fibonacci heap.
 
Entry<T> 
enqueue(T value, double priority)
Inserts the specified element into the Fibonacci heap with the specified
priority.
 
boolean 
isEmpty()
Returns whether the heap is empty.
 
static <T> FibonacciHeap<T> 
merge(FibonacciHeap<T> one, FibonacciHeap<T> two)
Given two Fibonacci heaps, returns a new Fibonacci heap that contains
all of the elements of the two heaps.
 
Entry<T> 
min()
Returns an Entry object corresponding to the minimum element of the
Fibonacci heap, throwing a NoSuchElementException if the heap is
empty.
 
int 
size()
Returns the number of elements in the heap.

[Expand]
Inherited Methods  

From class
java.lang.Object

Decreases the key of the specified element to the new priority. If the new priority is greater than the old priority, this function throws an IllegalArgumentException. The new priority must be a finite double, so you cannot set the priority to be NaN, or +/ infinity. Doing so also throws an IllegalArgumentException.
It is assumed that the entry belongs in this heap. For efficiency reasons, this is not checked at runtime.
entry  The element whose priority should be decreased. 

newPriority  The new priority to associate with this entry. 
IllegalArgumentException  If the new priority exceeds the old priority, or if the argument is not a finite double. 

Deletes this Entry from the Fibonacci heap that contains it.
It is assumed that the entry belongs in this heap. For efficiency reasons, this is not checked at runtime.
entry  The entry to delete. 

Dequeues and returns the minimum element of the Fibonacci heap. If the heap is empty, this throws a NoSuchElementException.
NoSuchElementException  If the heap is empty. 

Inserts the specified element into the Fibonacci heap with the specified priority. Its priority must be a valid double, so you cannot set the priority to NaN.
value  The value to insert. 

priority  Its priority, which must be valid. 
Returns whether the heap is empty.
Given two Fibonacci heaps, returns a new Fibonacci heap that contains all of the elements of the two heaps. Each of the input heaps is destructively modified by having all its elements removed. You can continue to use those heaps, but be aware that they will be empty after this call completes.
one  The first Fibonacci heap to merge. 

two  The second Fibonacci heap to merge. 
Returns an Entry object corresponding to the minimum element of the Fibonacci heap, throwing a NoSuchElementException if the heap is empty.
NoSuchElementException  If the heap is empty. 

Returns the number of elements in the heap.