ABSTRACT
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 algorithm and Dijkstra’s shortest path algorithm are dominated by the cost of increasing the priority of elements, the Fibonacci heap yields the theoretically best worst-case time complexities for these algorithms.
