| 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 (243 kB) |
| DOI: | 10.1007/978-3-642-28076-4_18 |
| 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 (Journal article) HTML (Source code) HTML (Errata) |
| BibLATEX: | @inproceedings{EK2012aC,
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},
}
|