We describe two new heap data structures. Our first structure, called the thin heap; is closely related to Fibonacci heaps [2] 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.

The second structure, called the fat heap, achieves the same asymptotic performance as the run-relaxed heaps described by Driscoll et al. [1] and offers an alternative to it in all its applications. Specifically, make-heap, insert, find-min, and decrease-key take O(1) worst-case time, and delete, delete-min, and meld take O(log n) worst-case time. Our data structure is much simpler than run-relaxed heaps.

There exists a well-known connection between binomial queue operations and arithmetic operations on binary numbers.

Our fat heaps exploit this connection and achieve their performance by incorporating two redundant counters.