goldman.collection.priority
Class FibonacciHeap<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.priority.PairingHeap<E>
          extended by goldman.collection.priority.FibonacciHeap<E>
All Implemented Interfaces:
Collection<E>, PriorityQueue<E>, Tracked<E>, Iterable<E>

public class FibonacciHeap<E>
extends PairingHeap<E>
implements PriorityQueue<E>, Tracked<E>

The Fibonacci heap is a more complex self-organizing data structure. It has amortized and worst-case costs for add and merge are constant. Increasing the priority of an element has amortized constant cost, but a worst-case logarithmic cost. Removing an element or lowering the priority of an element has logarithmic amortized cost, but the worst-case cost can be linear. It is a more complex data structure, so unless the priority is often increased, the overall time complexity is higher than that of the pairing heap. However, using a Fibonacci heap yields the asymptotically fastest implementation of Prim's minimum spanning tree algorithm and Dijkstra's shortest path algorithm.


Nested Class Summary
 
Nested classes/interfaces inherited from class goldman.collection.priority.PairingHeap
PairingHeap.Tracker
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, NOT_FOUND, size, version
 
Constructor Summary
FibonacciHeap()
           
FibonacciHeap(Comparator<? super E> comp)
           
 
Method Summary
protected  void increasePriority(goldman.collection.priority.PairingHeap.HeapNode<E> x, E element)
           
 String showStructure()
           
 
Methods inherited from class goldman.collection.priority.PairingHeap
add, addTracked, extractMax, getEquivalentElement, getLocator, iterator, max, remove, update
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, clear, compare, contains, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, traverseForVisitor, trimToSize, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.priority.PriorityQueue
extractMax, getLocator, max
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from interface goldman.collection.Tracked
addTracked
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize
 

Constructor Detail

FibonacciHeap

public FibonacciHeap()

FibonacciHeap

public FibonacciHeap(Comparator<? super E> comp)
Parameters:
comp - a user-provided comparator
Method Detail

increasePriority

protected void increasePriority(goldman.collection.priority.PairingHeap.HeapNode<E> x,
                                E element)
Parameters:
x - a reference to the heap node holding element e
element - the new element to replace e
REQUIRES: elementx.element and that x is not null

showStructure

public String showStructure()
Overrides:
showStructure in class PairingHeap<E>