2001-23: Generalized Pairing Heaps

DIMACS TR: 2001-23

Generalized Pairing Heaps

Authors: Amr Elmasry

ABSTRACT
We give a generalized form for the standard implementation of the pairing heaps. A new parameter k is introduced. When the node with the minimum value is to be deleted from the heap, the operations to combine the resulting sub-trees into one tree depend on the value of k. When the value of k is equal to 2, the implementation will be equivalent to the standard pairing heaps' implementation. We show that, for any constant k, this general form achieves the same bounds as the standard implementation. Finally, experimental results are conducted showing that, by tuning the value of k, the number of comparisons involved in this operation can be reduced.

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

DIMACS Home Page