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 ⌈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.

@article{EEK2017bJ,
author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
title = {Optimizing binary heaps},
journaltitle = {Theory of Computing Systems},
volume = {61},
number = {2},
year = {2017},
pages = {606--636},
}