The violation heap: a relaxed Fibonacci-like heap

DOI10.1007/978-3-642-14031-0_51MaRDI QIDQ3578348zbMATH OpenOpenAlexFDO

Authors Amr Elmasry

Publication date 20 July 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We give a priority queue that achieves the same amortized bounds as Fibonacci heaps. Namely, find-min requires O(1) worst-case time, insert, meld and decrease-key require O(1) amortized time, and delete-min requires $O(logn)$ amortized time. Our structure is simple and promises an efficient practical behavior when compared to other known Fibonacci-like heaps. The main idea behind our construction is to propagate rank updates instead of performing cascaded cuts following a decrease-key operation, allowing for a relaxed structure.

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

Cited in

(8)

• Strict Fibonacci heaps
• Linear-algebraic implementation of Fibonacci heap
• The violation heap: a relaxed Fibonacci-like heap
• Fat heaps without regular counters
• 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
• A survey on priority queues

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