作者
Amr Elmasry
发表日期
2010/7/19
图书
International Computing and Combinatorics Conference
页码范围
479-488
出版商
Springer Berlin Heidelberg
简介
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.
学术搜索中的文章
A Elmasry - International Computing and Combinatorics …, 2010
A Elmasry - CoRR, abs/0812.2851, 2008