Pairing heaps with O(log log n) decrease cost

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pairing heaps with O(log log n) decrease cost

Full text

Pdf (333 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 471-476

Year of Publication: 2009

Author

Amr Elmasry

Max-Planck Institut für Informatik, Saarbrücken, Germany

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 73, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

We give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by Fredman for a family of similar self-adjusting heaps. Namely, our heap structure requires O(1) for insert and findmin, O(log n) for delete-min, and O(log log n) for decrease-key and meld (all the bounds are in the amortized sense except for find-min).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Amr Elmasry, Parameterized self-adjusting heaps, Journal of Algorithms, v.52 n.2, p.103-119, August 2004 [doi>10.1016/j.jalgor.2004.03.002]
	2	A. Elmasry. Adaptive properties of pairing heaps. Technical Report 2001--29, DIMACS (2001).
	3	A. Elmasry and M. Fredman. Unpublished experiments. Rutgers University (1997).
	4	Michael L. Fredman, A Priority Queue Transform, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.243-257, July 19-21, 1999
	5	Michael L. Fredman, On the efficiency of pairing heaps and related data structures, Journal of the ACM (JACM), v.46 n.4, p.473-501, July 1999 [doi>10.1145/320211.320214]
	6	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]
	7	John Iacono, Improved Upper Bounds for Pairing Heaps, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.32-45, July 05-07, 2000
	8	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]
	9	B. Moret and H. Shapiro. An empirical assessment of algorithms for constructing a minimum spanning tree. DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science 15 (1994), pp. 99--117.
	10	Seth Pettie, Towards a Final Analysis of Pairing Heaps, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.174-183, October 23-25, 2005 [doi>10.1109/SFCS.2005.75]
	11	Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
	12	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
	13	John T. Stasko , Jeffrey Scott Vitter, Pairing heaps: experiments and analysis, Communications of the ACM, v.30 n.3, p.234-249, March 1987 [doi>10.1145/214748.214759]
	14	R. Tarjan. Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods 6 (1985), pp. 306--318.