| Fat heaps without regular counters | |
| Authors: | Amr Elmasry and Jyrki Katajainen |
| Published in: | Discrete Mathematics, Algorithms and Applications 5,2 (2013), Article 1360006, 21 pp. |
| Full text: |  PDF (227 kB) |
| DOI: | 10.1142/S1793830913600069 |
| Copyright: | © World Scientific Publishing Company |
| 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(log n) for delete and delete-min. Compared to the original, 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 (Conference paper) HTML (Source code) |
| BibLATEX: | @article{EK2013J,
author = {Amr Elmasry and Jyrki Katajainen},
title = {Fat heaps without regular counters},
journaltitle = {Discrete Mathematics, Algorithms and Applications},
volume = {5},
number = {2},
year = {2013},
articleno = {1360006},
pagetotal = {21},
}
|