TY - GEN
T1 - Strict Fibonacci heaps
AU - Brodal, Gerth Stølting
AU - Lagogiannis, George
AU - Tarjan, Robert E.
PY - 2012
Y1 - 2012
N2 - We present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(lg n) time, where n is the size of the heap. The data structure uses linear space. A previous, very complicated, solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld. We use the pigeonhole principle in place of the redundant counter mechanism.
AB - We present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(lg n) time, where n is the size of the heap. The data structure uses linear space. A previous, very complicated, solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld. We use the pigeonhole principle in place of the redundant counter mechanism.
KW - data structures
KW - decrease-key
KW - heaps
KW - meld
KW - worst-case complexity
UR - http://www.scopus.com/inward/record.url?scp=84862614330&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862614330&partnerID=8YFLogxK
U2 - 10.1145/2213977.2214082
DO - 10.1145/2213977.2214082
M3 - Conference contribution
AN - SCOPUS:84862614330
SN - 9781450312455
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1177
EP - 1184
BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12
Y2 - 19 May 2012 through 22 May 2012
ER -