Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Hollow Heaps
verfasst von : Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, Uri Zwick
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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(\log n)$$
O
(
log
n
)
amortized time. 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.