Strict Fibonacci heaps

Gerth Stølting Brodal, George Lagogiannis, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages1177-1184
Number of pages8
DOIs
StatePublished - Jun 26 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • data structures
  • decrease-key
  • heaps
  • meld
  • worst-case complexity

Fingerprint Dive into the research topics of 'Strict Fibonacci heaps'. Together they form a unique fingerprint.

  • Cite this

    Brodal, G. S., Lagogiannis, G., & Tarjan, R. E. (2012). Strict Fibonacci heaps. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 1177-1184). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214082