New Heap Data Structures
|Authors:||Kaplan, Haim, Tarjan, Robert E.|
We describe two new heap data structures. Our first structure, called the thin heap; is closely related to Fibonacci heaps  and has the same asymptotic performance. Specifically, make-heap, insert, find-min, decrease-key, and meld take O(1) amortized time, and delete-min and delete take O(log n) amortized time. The advantage of thin heaps over Fibonacci heaps is that the heap-ordered trees being maintained have more structure and require fewer fields per node, but the operations are as simple as for Fibonacci heaps. In a practical implementation, the time and space constant factors of thin heaps should thus be better than those of Fibonacci heaps.