Two-tier relaxed heaps
Authors:Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Published in:Proceedings of the 17th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 4288, Springer-Verlag (2006), 308-317
Full text:<pdf.gif>PDF (126 kB)  <ps.gif>PS (567 kB)  
Copyright:© Springer-Verlag

We introduce an adaptation of run-relaxed heaps which provides efficient heap operations with respect to the number of element comparisons performed. Our data structure guarantees the worst-case cost of O(1) for find-min, insert, and decrease; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for delete, improving the bound of 3 lg n + O(1) on the number of element comparisons known for run-relaxed heaps. Here, n denotes the number of elements stored prior to the operation in question, and lg n equals max{1, log2 n}.

Related:<html.gif>HTML (Journal article)  
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Two-tier relaxed heaps},
  booktitle = {Proceedings of the 17th International Symposium on Algorithms
    and Computation},
  series = {Lecture Notes in Computer Science},
  volume = {4288},
  publisher = {Springer-Verlag},
  year = {2006},
  pages = {308--317},
This page was generated by Jyrki Katajainen <> on 31.12.2011.