A Practical Guide to Data Structures and Algorithms using Java

PriorityQueue

Chapter 28

Fibonacci Heap Data Structure

AbstractCollection<E> implements Collection<E>

↑

PairingHeap<E> implements PriorityQueue<E>, Tracked<E>

↑

FibonacciHeap<E> implements PriorityQueue<E>, Tracked<E>

Uses: Java references

Used By: TaggedFibonacciHeap (Section 49.8.5)

Strengths: The Fibonacci heap is theoretically the best data structure. It is the only priority queue

data structure with constant amortized cost for merging two priority queues, and also increasing the

priority of an element through a locator. The pairing heap, in contrast, has a logarithmic amortized

cost for both of these operations. Since Prim’s minimum spanning tree