The violation heap: a relaxed Fibonacci-like heap

DOI10.1142/S1793830910000838MaRDI QIDQ3084682zbMATH OpenOpenAlexFDO

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)

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

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)