Let n denote the number of elements currently in a data structure.
An in-place heap is stored in
the first n locations of an array, uses O(1) extra space, and
supports the operations: minimum, insert, and
extract-min. We introduce an in-place heap, for which minimum
and insert take O(1) worst-case time, and extract-min takes
O(lg n) worst-case time and involves at most lg n + O(1)
The achieved bounds are optimal to within additive constant terms
for the number of element comparisons. In
particular, these bounds for both insert and extract-min—and
the time bound for insert—surpass the corresponding lower bounds
known for binary heaps, though our data structure is similar.
In a binary heap, when viewed as a nearly complete
binary tree, every node other than the root obeys the heap
property, i.e. the element at a node is not smaller than that at its
parent. To surpass the lower bound for extract-min, we reinforce a
stronger property at the bottom levels of the heap that the element at
any right child is not smaller than that at its left sibling. To
surpass the lower bound for insert, we buffer insertions and
allow O(lg2 n) nodes to
violate heap order in relation to their parents.