Optimizing Binary Heaps

A priority queue—a data structure supporting, inter alia, the operations minimum (top), insert (push), and extract-min (pop)—is said to operate in-place if it uses O(1) extra space in addition to the n elements stored at the beginning of an array. Prior to this work, no in-place priority queue was known to provide worst-case guarantees on the number of element comparisons that are optimal up to additive constant terms for both insert and extract-min. In particular, for the standard implementation of binary heaps, insert and extract-min operate in logarithmic time while involving at most ceil(lg n) and 2 lg n [could possibly be reduced to lg lg n + O(1) and lg n + log^∗ n + O(1)] element comparisons, respectively. In this paper we propose a variant of a binary heap that operates in-place, executes minimum and insert in O(1) worst-case time, and extract-min in O(lg n) worst-case time while involving at most lg n + O(1) element comparisons. These efficiencies surpass lower bounds known for binary heaps, thereby resolving a long-standing theoretical debate.