A binary heap is a classical in-place priority queue described in most textbooks on data structures and algorithms. A binary heap is known to support insert and extract-min in O(lg n) worst-case time, where n denotes the number of elements stored in the data structure. We introduce an in-place variant of binary heaps that supports insert in O(1) time, and extract-min in O(lg n) time with at most lg n + O(1) element comparisons, all in the amortized sense. Our construction is conceptually simple and can be presented in basic textbooks. Furthermore, we show how to support insert in O(1) worst-case time and simultaneously support extract-min as efficiently as binary heaps. Finally, we show how a sequence of extract-min operations can be performed in-place using at most lg n + O(1) element comparisons per operation after linear preprocessing. The upper bounds we prove bypass the lower bounds known for both the insert and extract-min operations of binary heaps.

@report{EK2013R,
  author = {Amr Elmasry and Jyrki Katajainen},
  title = {Towards ultimate binary heaps},
  type = {CPH STL Report},
  number = {2013-1},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2013},
  pagetotal = {13},
}