New Heap Data Structures

Abstract:

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.