2012/05/19 by Gerth Stølting Brodal, George Lagogiannis, Robert E. Tarjan · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Geometric and Algebraic Topology #semigroups and automata theory
paper · doi:10.1145/2213977.2214082
openalex publication_date 2012/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.