public final class

FibonacciHeap

extends Object
java.lang.Object
   ↳ es.usc.citius.lab.hipster.collections.FibonacciHeap<T>

Class Overview

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 decrease-key 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 decrease-key to gain significant performance boosts. For example, Dijkstra's algorithm for single-source 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, doubly-linked list of trees obeying the min-heap 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 doubly-linked 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=fibonacci-heap

Summary

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

Public Constructors

public FibonacciHeap ()

Public Methods

public void decreaseKey (Entry<T> entry, double newPriority)

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.

Parameters
entry The element whose priority should be decreased.
newPriority The new priority to associate with this entry.
Throws
IllegalArgumentException If the new priority exceeds the old priority, or if the argument is not a finite double.

public void delete (Entry<T> entry)

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.

Parameters
entry The entry to delete.

public Entry<T> dequeueMin ()

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

Returns
  • The smallest element of the Fibonacci heap.
Throws
NoSuchElementException If the heap is empty.

public Entry<T> enqueue (T value, double priority)

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.

Parameters
value The value to insert.
priority Its priority, which must be valid.
Returns
  • An Entry representing that element in the tree.

public boolean isEmpty ()

Returns whether the heap is empty.

Returns
  • Whether the heap is empty.

public static 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. 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.

Parameters
one The first Fibonacci heap to merge.
two The second Fibonacci heap to merge.
Returns
  • A new FibonacciHeap containing all of the elements of both heaps.

public Entry<T> min ()

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

Returns
  • The smallest element of the heap.
Throws
NoSuchElementException If the heap is empty.

public int size ()

Returns the number of elements in the heap.

Returns
  • The number of elements in the heap.