Hollow Heaps

DOI10.1007/978-3-662-47672-7_56MaRDI QIDQ3448827zbMATH OpenOpenAlexWikidataFDO

Authors Thomas Dueholm Hansen, Haim Kaplan, Uri Zwick, Robert E. Tarjan

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.06535

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take $O(1)$ time, worst case as well as amortized; delete and delete-min take $O(logn)$ amortized time on a heap of $n$ items. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.

Recommendations

• Hollow heaps
• scientific article; zbMATH DE number 4014031
• Thin heaps, thick heaps
• Heaps on Heaps
• Borel on the heap
• scientific article; zbMATH DE number 3880723
• Giant holes
• Algorithm Theory - SWAT 2004
• scientific article; zbMATH DE number 1555945

Cites work

• A note on two problems in connexion with graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 871899 (Why is no real title available?)
• Meldable heaps and boolean union-find
• Optimum branchings
• Quake heaps: a simple alternative to Fibonacci heaps
• Rank-pairing heaps
• Strict Fibonacci heaps
• The violation heap: a relaxed Fibonacci-like heap
• Theory of 2-3 heaps
• Thin heaps, thick heaps

Cited in

(12)

• Available stabilizing heaps
• Theory of 2-3 heaps
• scientific article; zbMATH DE number 1696652 (Why is no real title available?)
• Quake heaps: a simple alternative to Fibonacci heaps
• scientific article; zbMATH DE number 4014031 (Why is no real title available?)
• Hollow heaps
• Bipartite binomial heaps
• Thin heaps, thick heaps
• Smooth heaps and a dual view of self-adjusting data structures
• A simple array version of M-heap
• Strict Fibonacci heaps
• M-Heap: A Modified Heap Data Structure

This page was built for publication: Hollow Heaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448827)