Towards ultimate binary heaps
Authors:Amr Elmasry and Jyrki Katajainen
Publication:CPH STL Report 2013-1, Department of Computer Science, University of Copenhagen (2013), 13 pp.
Full text:<pdf.gif>PDF (181 kB)  

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.

Related:<html.gif>HTML (Slides)  
  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},
This page was generated by Jyrki Katajainen <> on 19.01.2014.