Two-tier relaxed heaps
Authors:Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Published in:Acta Informatica 45,3 (2008), 193-210
Full text:<pdf.gif>PDF (197 kB)  <ps.gif>PS (446 kB)  
Copyright:© Springer-Verlag

We introduce a data structure which provides efficient heap operations with respect to the number of element comparisons performed. Let n denote the size of the heap being manipulated. Our data structure guarantees the worst-case cost of O(1) for finding the minimum, inserting an element, extracting an (unspecified) element, and replacing an element with a smaller element; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for deleting an element. We thereby improve the comparison complexity of heap operations known for run-relaxed heaps and other worst-case efficient heaps. Furthermore, our data structure supports melding of two heaps of size m and n at the worst-case cost of O(min{lg m, lg n}).

Related:<html.gif>HTML (Errata)  
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Two-tier relaxed heaps},
  journaltitle = {Acta Informatica},
  volume = {45},
  number = {3},
  year = {2008},
  pages = {193--210},
This page was generated by Jyrki Katajainen <> on 09.11.2012.