The violation heap: a relaxed Fibonacci-like heap

DOI10.1142/S1793830910000838zbMATH Open1211.68128OpenAlexW2040934527MaRDI QIDQ3084682FDOQ3084682

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

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

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)

Cites Work

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

Cited In (12)

• 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
• 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)