Abstract
We introduce two data-structural transformations to construct double-ended priority queues from priority queues. To apply our transformations the priority queues exploited must support the extraction of an unspecified element, in addition to the standard priority-queue operations. With the first transformation we obtain a double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; and the worst-case cost of O(lg n) with at most lg n + O(1) element comparisons for delete. With the second transformation we get a meldable double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; the worst-case cost of O(lg n) with at most lg n + O(lg lg n) element comparisons for delete; and the worst-case cost of O(min {lg m, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alstrup S, Husfeld T, Rauhe T, Thorup M (2005) Black box for constant-time insertion in priority queues. ACM Trans Algorithms 1: 102–106
Arvind A, Pandu Rangan C (1999) Symmetric min-max heap: a simpler data structure for double-ended priority queue. Inf Process Lett 69: 197–199
Atkinson MD, Sack J-R, Santoro N, Strothotte T (1986) Min-max heaps and generalized priority queues. Commun ACM 29: 996–1000
Blum M, Floyd RW, Pratt V, Rivest RL, Tarjan RE (1973) Time bounds for selection. J Comput Syst Sci 7: 448–461
Brodal GS (1995) Fast meldable priority queues. In: Proceedings of the 4th international workshop on algorithms and data structures. Lecture notes in computer science, vol 955. Springer, Berlin, pp 282–290
Brodal GS (1996) Worst-case efficient priority queues. In: Proceedings of the 7th ACM-SIAM symposium on discrete algorithms. ACM/SIAM, New York/Philadelphia, pp 52–58
Carlsson S (1987) The deap—a double-ended heap to implement double-ended priority queues. Inf Process Lett 26: 33–36
Chang SC, Du MW (1993) Diamond deque: a simple data structure for priority deques. Inf Process Lett 46: 231–237
Cho S, Sahni S (1999) Mergeable double-ended priority queues. Int J Found Comput Sci 10: 1–18
Chong K-R, Sahni S (2000) Correspondence-based data structures for double-ended priority queues. ACM J Exp Algorithmics 5: article
Ding Y, Weiss MA (1993) The relaxed min-max heap: a mergeable double-ended priority queue. Acta Inform 30: 215–231
Elmasry A, Jensen C, Katajainen J (2008) Multipartite priority queues. ACM Trans Algorithms (to appear)
Elmasry A, Jensen C, Katajainen J (2008) Two-tier relaxed heaps. Acta Inform 45: 193–210
Goodrich MT, Tamassia R (2002) Algorithm design: foundations, analysis, and internet examples. Wiley, Hoboken
Hagerup T (1998) Sorting and searching on the word RAM. In: Proceedings of the 15th annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 1373. Springer, Berlin, pp 366–398
Horowitz E, Sahni S, Rajasekaran S (1998) Computer algorithms/C++. Computer Science Press, New York
Høyer P (1995) A general technique for implementation of efficient priority queues. In: Proceedings of the 3rd Israel symposium on the theory of computing and systems, IEEE, Los Alamitos, pp 57–66
Katajainen J, Vitale F (2003) Navigation piles with applications to sorting, priority queues, and priority deques. Nordic J Comput 10: 238–262
Khoong CM, Leong HW (1993) Double-ended binomial queues. In: Proceedings of the 4th international symposium on algorithms and computation. Lecture notes in computer science, vol 762. Springer, Berlin, pp 128–137
Leeuwen J, Wood D (1993) Interval heaps. Comput J 36: 209–216
Makris C, Tsakalidis A, Tsichlas K (2003) Reflected min-max heaps. Inf Process Lett 86: 209–214
Mortensen CW, Pettie S (2005) The complexity of implicit and space-efficient priority queues. In: Proceedings of the 9th workshop on algorithms and data structures. Lecture notes in computer science, vol 3608. Springer, Berlin, pp 49–60
Nath SK, Chowdhury RA, Kaykobad M (2000) Min-max fine heaps. arXiv.org e-Print archive article cs.DS/0007043. http://arxiv.org
Olariu S, Overstreet CM, Wen Z (1991) A mergeable double-ended priority queue. Comput J 34: 423–427
Rahman MZ, Chowdhury RA, Kaykobad M (2003) Improvements in double ended priority queues. Int J Comput Math 80: 1121–1129
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of the authors was partially supported by the Danish Natural Science Research Council under contracts 21-02-0501 (project Practical data structures and algorithms) and 272-05-0272 (project Generic programming—algorithms and tools). A. Elmasry was supported by Alexander von Humboldt fellowship.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Elmasry, A., Jensen, C. & Katajainen, J. Two new methods for constructing double-ended priority queues from priority queues. Computing 83, 193–204 (2008). https://doi.org/10.1007/s00607-008-0019-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-008-0019-2
Keywords
- Data structures
- Priority queues
- Double-ended priority queues
- Min-max priority queues
- Priority deques
- Meticulous analysis
- Comparison complexity