Pairing heaps: experiments and analysis

ABSTRACT

The pairing heap has recently been introduced as a new data structure for priority queues. Pairing heaps are extremely simple to implement and seem to be very efficient in practice, but they are difficult to analyze theoretically, and open problems remain. It has been conjectured that they achieve the same amortized time bounds as Fibonacci heaps, namely, O(log n) time for delete and delete_min and O(1) for all other operations, where n is the size of the priority queue at the time of the operation. We provide empirical evidence that supports this conjecture. The most promising algorithm in our simulations is a new variant of the twopass method, called auxiliary twopass. We prove that, assuming no decrease_key operations are performed, it achieves the same amortized time bounds as Fibonacci heaps.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Brown. M.R. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7 (Aug. 1978), 298-319.
• 3: Crane, C.A. Linear lists and priority queues as balanced binary trees. Tech. Rep. STAN-CS-72259, Dept. of Computer Science, Stanford University, Feb. 1972.
• 4: Fredman, M.L., and Tarjan. R.E. Fibonacci heaps and their uses in improved network optimization algorithms. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, (West Palm Beach, Fla.. Oct. 1984), 338-344.
• 5: Michael L. Fredman , Robert Sedgewick , Daniel D. Sleator , Robert E. Tarjan, The pairing heap: a new form of self-adjusting heap, Algorithmica, v.1 n.1, p.111-129, Jan. 1986 [doi>10.1007/BF01840439]
• 6: Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986 [doi>10.1145/5684.5686]
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: Tarjan. R.E. Amortized computational complexity. SIAM J Algorithm Disc. Mefh. 6 (Apr. 1985). 306-316.
• 9: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]
• 10: Williams, J.W.J. Algorithm 232: Heapsort. Commun. ACM 7, 6 (June 1964),347-348.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  E. Data

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

General Terms:
Algorithms, Design, Performance, Theory