Let n denote the number of elements currently in a data structure.
An inplace heap is stored in
the first n locations of an array, uses O(1) extra space, and
supports the operations: minimum, insert, and
extractmin. We introduce an inplace heap, for which minimum
and insert take O(1) worstcase time, and extractmin takes
O(lg n) worstcase time and involves at most lg n + O(1)
element comparisons.
The achieved bounds are optimal to within additive constant terms
for the number of element comparisons. In
particular, these bounds for both insert and extractmin—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 extractmin, 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(lg^{2} n) nodes to
violate heap order in relation to their parents.
