作者
Amr Elmasry
发表日期
2004/7/8
研讨会论文
Scandinavian Workshop on Algorithm Theory
页码范围
212-222
出版商
Springer, Berlin, Heidelberg
简介
We introduce a framework for reducing the number of comparisons performed in the deletion and minimum deletion operations for priority queues. In particular, we give a priority queue with constant cost per insertion and minimum finding, and logarithmic cost with at most logn+O(loglogn) comparisons per deletion and minimum deletion, improving over the bound of 2 logn+O(1) comparisons for the binomial queues and the pairing heaps. We also give a priority queue that supports, in addition to the above operations, the decrease-key operation. This latter priority queue achieves, in the amortized sense, constant cost per insertion, minimum finding and decrease-key operations, and logarithmic cost with at most 1.44logn+O(loglogn) comparisons per deletion and minimum deletion.
学术搜索中的文章
A Elmasry, C Jensen, J Katajainen
A Elmasry, C Jensen, J Katajainen - CPH STL TR 2004, 2004