Fat heaps without regular counters
Authors:Amr Elmasry and Jyrki Katajainen
Published in:Proceedings of the 6th Workshop on Algorithms and Computation, Lecture Notes in Computer Science 7157, Springer-Verlag (2012), 173-185
Full text:<pdf.gif>PDF (243 kB)  
Copyright:© Springer-Verlag
Abstract:We introduce a variant of fat heaps that does not rely on regular counters, and still achieves the optimal worst-case bounds: O(1) for find-min, insert and decrease, and O(lg n) for delete and delete-min. Our variant is simpler to explain, more efficient, and easier to implement. Experimental results suggest that our implementation is superior to structures, like run-relaxed heaps, that achieve the same worst-case bounds, and competitive to structures, like Fibonacci heaps, that achieve the same bounds in the amortized sense.
Related:<html.gif>HTML (Journal article)  <html.gif>HTML (Source code)  <html.gif>HTML (Errata)  
  author = {Amr Elmasry and Jyrki Katajainen},
  title = {Fat heaps without regular counters},
  booktitle = {Proceedings of the 6th Workshop on Algorithms and Computation},
  series = {Lecture Notes in Computer Science},
  volume = {7157},
  publisher = {Springer-Verlag},
  year = {2012},
  pages = {173--185},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 22.05.2015.