English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

The Violation Heap: A Relaxed Fibonacci-Like Heap

MPS-Authors
/persons/resource/persons44380

Elmasry,  Amr
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (public)

arXiv:0812.2851.pdf
(Preprint), 137KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Elmasry, A. (2008). The Violation Heap: A Relaxed Fibonacci-Like Heap. Retrieved from http://arxiv.org/abs/0812.2851.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0028-F4FF-7
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(\log n)$ 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.