goldman.collection.priority
Class FibonacciHeap<E>
java.lang.Object
goldman.collection.AbstractCollection<E>
goldman.collection.priority.PairingHeap<E>
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.
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 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.Collection |
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
FibonacciHeap
public FibonacciHeap()
FibonacciHeap
public FibonacciHeap(Comparator<? super E> comp)
- Parameters:
comp
- a user-provided comparator
increasePriority
protected void increasePriority(goldman.collection.priority.PairingHeap.HeapNode<E> x,
E element)
- Parameters:
x
- a reference
to the heap node holding
element eelement
- the new element to replace e
REQUIRES:
element
≥ x.element
and
that x
is not null
showStructure
public String showStructure()
- Overrides:
showStructure
in class PairingHeap<E>