2008/12/15 by Amr Elmasry, Elmasry, Amr
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.0812.2851
openalex publication_date 2008/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.