Violation Heaps: A Better Substitute for Fibonacci Heaps
Amr Elmasry · 2008
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 a more efficient practical behavior compared to any other known Fibonacci-like heap.