## 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