The Complexity of Priority Queue Maintenance

A notion of priority queue efficiency is defined, based on comparison counting. A good lower bound on the average and worst case number of comparisons is derived; several priority queue algorithms are exhibited which nearly attain the bound. It is shown that one of these algorithms, using binomial queues, can be characterized in a simple way based on the number and type of comparisons that it requires. The proof of this result involves an interesting problem on trees for which Huffman's construction gives a solution.

Authors

• Mark R. Brown

Keywords

No keywords are indexed for this paper.