Fat heaps without regular counters

TY - GEN

T1 - Fat heaps without regular counters

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

N1 - Conference code: 6

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-28076-4_18

DO - 10.1007/978-3-642-28076-4_18

M3 - Article in proceedings

SN - 978-3-642-28075-7

T3 - Lecture notes in computer science

SP - 173

EP - 185

BT - WALCOM: Algorithms and Computation

A2 - Rahman, Md. Saidur

A2 - Nakano, Shin-ichi

PB - Springer

T2 - 6th International Workshop on Algorithms and Computation

Y2 - 15 February 2012 through 17 February 2012

ER -