Thin Heaps, Thick Heaps
The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of Hoyer [1995], we describe three heap implementations (two versions of thin heaps and one of thick heaps) that have the same amortized efficiency as Fibonacci heaps, but need less space and promise better practical performance. As part of our development, we fill in a gap in Hoyer's analysis.
thin heap heap thick heap fibonacci heap data structure priority queue binomial queue melding decrease key operation