The violation heap: a relaxed Fibonacci-like heap

DOI10.1142/S1793830910000838MaRDI QIDQ3084682zbMATHOpenAlexFDO

Authors Amr Elmasry

Publication date 25 March 2011

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830910000838

zbMATH Keywords

data structurespriority queuesamortized analysis decrease keyFibonacci heaps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10) Algorithms in computer science (68W99)

Recommendations

• The violation heap: a relaxed Fibonacci-like heap
• Strict Fibonacci heaps
• Quake heaps: a simple alternative to Fibonacci heaps
• Rank-Pairing Heaps
• Replacing mark bits with randomness in Fibonacci heaps

Cites work

• A data structure for manipulating priority queues
• Introduction to algorithms
• On the efficiency of pairing heaps and related data structures
• Self-adjusting binary search trees
• The pairing heap: A new form of self-adjusting heap
• Theory of 2-3 heaps
• Two-tier relaxed heaps

Cited in

(12)

• Pairing heaps: the forward variant
• Fat heaps without regular counters
• Fat heaps without regular counters
• Hollow Heaps
• Linear-algebraic implementation of Fibonacci heap
• Why some heaps support constant-amortized-time decrease-key operations, and others do not
• The violation heap: a relaxed Fibonacci-like heap
• Strict Fibonacci heaps
• Smooth heaps and a dual view of self-adjusting data structures
• Quake heaps: a simple alternative to Fibonacci heaps
• Replacing mark bits with randomness in Fibonacci heaps
• Hollow heaps

This page was built for publication: The violation heap: a relaxed Fibonacci-like heap

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