2004-21: A Framework for Reducing Comparisons in Heap Operations

DIMACS TR: 2004-21

A Framework for Reducing Comparisons in Heap Operations

Author: Amr Elmasry

ABSTRACT 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 $\log{n}+O(\log{\log{n}})$ \footnote{$\log{x}$ equals $\max(\log_2{x},1)$.} comparisons per deletion and minimum deletion, improving over the bound of $2 \log{n}+O(1)$ comparisons for the binomial queues and the pairing heaps. We further improve this bound to at most $\log{n}+O(1)$ comparisons. 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.44\log{n}+O(\log{\log{n}})$ comparisons per deletion and minimum deletion.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-21.ps.gz

DIMACS Home Page