Abstract
Back in 1964 Williams introduced the binary heap as a basic priority queue data structure supporting the operations Insert and ExtractMin in logarithmic time. Since then numerous papers have been published on priority queues. This paper tries to list some of the directions research on priority queues has taken the last 50 years.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Commun. ACM 31(9), 1116–1127 (1988)
Alstrup, S., Husfeldt, T., Rauhe, T., Thorup, M.: Black box for constant-time insertion in priority queues (note). ACM Trans. Algorithms 1(1), 102–106 (2005)
Andersson, A., Thorup, M.: Tight(er) worst-case bounds on dynamic searching and priority queues. In: Proc. 32nd ACM Symposium on Theory of Computing, pp. 335–342. ACM (2000)
Arge, L.: The buffer tree: A technique for designing batched external data structures. Algorithmica 37, 1–24 (2003)
Arge, L., Bender, M.A., Demaine, E.D., Holland-Minkley, B., Munro, J.I.: An optimal cache-oblivious priority queue and its application to graph algorithms. SIAM J. Comput. 36(6), 1672–1695 (2007)
Arvind, A., Rangan, C.P.: Symmetric min-max heap: A simpler data structure for double-ended priority queue. Inf. Process. Lett. 69(4), 197–199 (1999)
Asano, T., Elmasry, A., Katajainen, J.: Priority queues and sorting for read-only data. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 32–41. Springer, Heidelberg (2013)
Atkinson, M.D., Sack, J.R., Santoro, N., Strothotte, T.: Min-max heaps and generalized priority queues. Commun. ACM 29(10), 996–1000 (1986)
Beame, P.: A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput. 20(2), 270–277 (1991)
Bollobás, B., Simon, I.: Repeated random insertion into a priority queue. J. Algorithms 6(4), 466–477 (1985)
Brodal, G.S.: Fast meldable priority queues. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 282–290. Springer, Heidelberg (1995)
Brodal, G.S.: Worst-case efficient priority queues. In: Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58. SIAM (1996)
Brodal, G.S., Fagerberg, R.: Funnel heap - a cache oblivious priority queue. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 219–228. Springer, Heidelberg (2002)
Brodal, G.S., Fagerberg, R., Meyer, U., Zeh, N.: Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 480–492. Springer, Heidelberg (2004)
Brodal, G.S., Katajainen, J.: Worst-case efficient external-memory priority queues. In: Arnborg, S. (ed.) SWAT 1998. LNCS, vol. 1432, pp. 107–118. Springer, Heidelberg (1998)
Brodal, G.S., Lagogiannis, G., Tarjan, R.E.: Strict Fibonacci heaps. In: Proc. 44th ACM Symposium on Theory of Computing, pp. 1177–1184. ACM (2012)
Brodal, G.S., Okasaki, C.: Optimal purely functional priority queues. J. Funct. Program. 6(6), 839–857 (1996)
Brodnik, A., Carlsson, S., Fredman, M.L., Karlsson, J., Munro, J.I.: Worst case constant time priority queue. J. Systems and Software 78(3), 249–256 (2005)
Brodnik, A., Karlsson, J., Munro, J.I., Nilsson, A.: An O(1) solution to the prefix sum problem on a specialized memory architecture. In: Navarro, G., Bertossi, L., Kohayakawa, Y. (eds.) TCS 2006. IFIP, vol. 209, pp. 103–114. Springer, Boston (2006)
Brown, M.R.: Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7(3), 298–319 (1978)
Carlsson, S.: The deap - a double-ended heap to implement double-ended priority queues. Inf. Process. Lett. 26(1), 33–36 (1987)
Carlsson, S., Chen, J.: The complexity of heaps. In: Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 393–402. SIAM (1992)
Carlsson, S., Chen, J., Strothotte, T.: A note on the construction of data structure “deap”. Inf. Process. Lett. 31(6), 315–317 (1989)
Carlsson, S., Munro, J.I., Poblete, P.V.: An implicit binomial queue with constant insertion time. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 1–13. Springer, Heidelberg (1988)
Chan, T.M.: Quake heaps: a simple alternative to Fibonacci heaps. Manuscript (2009)
Chang, S.C., Du, M.W.: Diamond deque: A simple data structure for priority deques. Inf. Process. Lett. 46(5), 231–237 (1993)
Chazelle, B.: A minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM 47(6), 1028–1047 (2000)
Chazelle, B.: The soft heap: an approximate priority queue with optimal error rate. J. ACM 47(6), 1012–1027 (2000)
Cherkassky, B.V., Goldberg, A.V., Silverstein, C.: Buckets, heaps, lists, and monotone priority queues. SIAM J. Comput. 28(4), 1326–1346 (1999)
Cho, S., Sahni, S.: Weight-biased leftist trees and modified skip lists. ACM J. Experimental Algorithmics 3, 2 (1998)
Cho, S., Sahni, S.: Mergeable double-ended priority queues. Int. J. Found. Comput. Sci. 10(1), 1–18 (1999)
Chong, K., Sahni, S.: Correspondence-based data structures for double-ended priority queues. ACM J. Experimental Algorithmics 5, 2 (2000)
Clancy, M.J., Knuth, D.E.: A programming and problem-solving seminar. Tech. Rep. Technical Report STAN-CS-77-606, Computer Science Department, Stanford University (1977)
Crane, C.A.: Linear lists and priority queues as balanced binary trees. Ph.D. thesis, Stanford University, Stanford, CA, USA (1972)
Ding, Y., Weiss, M.A.: The K-D heap: An efficient multi-dimensional priority queue. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol. 709, pp. 302–313. Springer, Heidelberg (1993)
Ding, Y., Weiss, M.A.: The relaxed min-max heap. Acta Inf. 30(3), 215–231 (1993)
Ding, Y., Weiss, M.A.: On the complexity of building an interval heap. Inf. Process. Lett. 50(3), 143–144 (1994)
Doberkat, E.E.: Deleting the root of a heap. Acta Inf. 17, 245–265 (1982)
Doberkat, E.E.: An average case analysis of floyd’s algorithm to construct heaps. Information and Control 61(2), 114–131 (1984)
Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31(11), 1343–1354 (1988)
Dutton, R.D.: Weak-heap sort. BIT 33(3), 372–381 (1993)
Edelkamp, S., Elmasry, A., Katajainen, J.: A catalogue of algorithms for building weak heaps. In: Smyth, B. (ed.) IWOCA 2012. LNCS, vol. 7643, pp. 249–262. Springer, Heidelberg (2012)
Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap data structure: Variants and applications. J. Discrete Algorithms 16, 187–205 (2012)
Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap family of priority queues in theory and praxis. In: Proc. 18th Computing: The Australasian Theory Symposium, CRPIT, vol. 128, pp. 103–112. Australian Computer Society (2012)
Edelkamp, S., Elmasry, A., Katajainen, J.: Ultimate binary heaps (submitted, 2013)
Edelkamp, S., Stiegeler, P.: Implementing HEAPSORT with (n logn − 0.9n) and QUICKSORT with (nlogn + 0.2n) comparisons. ACM J. Experimental Algorithmics 7, 5–24 (2002)
Edelkamp, S., Wegener, I.: On the performance of weak-heapsort. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 254–266. Springer, Heidelberg (2000)
Elmasry, A.: Layered heaps. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 212–222. Springer, Heidelberg (2004)
Elmasry, A.: Parameterized self-adjusting heaps. J. Algorithms 52(2), 103–119 (2004)
Elmasry, A.: A priority queue with the working-set property. Int. J. Found. Comput. Sci. 17(6), 1455–1466 (2006)
Elmasry, A.: Pairing heaps with O(loglogn) decrease cost. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 471–476. SIAM (2009)
Elmasry, A.: Pairing heaps with costless meld. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 183–193. Springer, Heidelberg (2010)
Elmasry, A.: The violation heap: A relaxed Fibonacci-like heap. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 479–488. Springer, Heidelberg (2010)
Elmasry, A., Farzan, A., Iacono, J.: A priority queue with the time-finger property. J. Discrete Algorithms 16, 206–212 (2012)
Elmasry, A., Jensen, C., Katajainen, J.: On the power of structural violations in priority queues. In: Proc. 13th Computing: The Australasian Theory Symposium, CRPIT, vol. 65, pp. 45–53. Australian Computer Society (2007)
Elmasry, A., Jensen, C., Katajainen, J.: Multipartite priority queues. ACM Trans. Algorithms 5(1) (2008)
Elmasry, A., Jensen, C., Katajainen, J.: Two new methods for constructing double-ended priority queues from priority queues. Computing 83(4), 193–204 (2008)
Elmasry, A., Jensen, C., Katajainen, J.: Two-tier relaxed heaps. Acta Inf. 45(3), 193–210 (2008)
Elmasry, A., Katajainen, J.: Worst-case optimal priority queues via extended regular counters. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 125–137. Springer, Heidelberg (2012)
van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6(3), 80–82 (1977)
van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory 10, 99–127 (1977)
Fadel, R., Jakobsen, K.V., Katajainen, J., Teuhola, J.: Heaps and heapsort on secondary storage. Theoretical Computer Science 220(2), 345–362 (1999)
Fagerberg, R.: A generalization of binomial queues. Inf. Process. Lett. 57(2), 109–114 (1996)
Fischer, M.J., Paterson, M.: Fishspear: A priority queue algorithm. J. ACM 41(1), 3–30 (1994)
Floyd, R.W.: Algorithm 113: Treesort. Commun. ACM 5(8), 434 (1962)
Floyd, R.W.: Algorithm 245: Treesort3. Commun. ACM 7(12), 701 (1964)
Ford Jr., L.R., Johnson, S.M.: A tournament problem. The American Mathematical Monthly 66(5), 387–389 (1959)
Franceschini, G., Grossi, R.: Optimal worst-case operations for implicit cache-oblivious search trees. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 114–126. Springer, Heidelberg (2003)
Franceschini, G., Grossi, R., Munro, J.I., Pagli, L.: Implicit B-trees: a new data structure for the dictionary problem. J. Comput. Syst. Sci. 68(4), 788–807 (2004)
Franceschini, G., Munro, J.I.: Implicit dictionaries with O(1) modifications per update and fast search. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithm, pp. 404–413. SIAM (2006)
Frederickson, G.N.: Implicit data structures for the dictionary problem. J. ACM 30(1), 80–94 (1983)
Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci. 34(1), 19–26 (1987)
Frederickson, G.N.: An optimal algorithm for selection in a min-heap. Inf. Comput. 104(2), 197–214 (1993)
Fredman, M.L.: On the efficiency of pairing heaps and related data structures. J. ACM 46(4), 473–501 (1999)
Fredman, M.L.: A priority queue transform. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol. 1668, pp. 244–258. Springer, Heidelberg (1999)
Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: A new form of self-adjusting heap. Algorithmica 1(1), 111–129 (1986)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)
Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424–436 (1993)
Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. 40th Foundations of Computer Science, pp. 285–297. IEEE (1999)
Gonnet, G.H., Munro, J.I.: Heaps on heaps. SIAM J. Comput. 15(4), 964–971 (1986)
Haeupler, B., Sen, S., Tarjan, R.E.: Rank-pairing heaps. SIAM J. Comput. 40(6), 1463–1485 (2011)
Han, Y.: Deterministic sorting in O(nloglogn) time and linear space. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 602–608. ACM (2002)
Han, Y., Thorup, M.: Integer sorting in \(O(n\sqrt{\log\log n})\) expected time and linear space. In: Proc. 43rd Foundations of Computer Science, pp. 135–144. IEEE (2002)
Harvey, N.J.A., Zatloukal, K.C.: The post-order heap. In: Proc. 3rd International Conference on Fun with Algorithms (2004)
Høyer, P.: A general technique for implementation of efficient priority queues. In: Proc. 3rd Israel Symposium on Theory of Computing and Systems, pp. 57–66. IEEE (1995)
Iacono, J.: Improved upper bounds for pairing heaps. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 32–45. Springer, Heidelberg (2000)
Iacono, J., Langerman, S.: Queaps. Algorithmica 42(1), 49–56 (2005)
Johnson, D.B.: Priority queues with update and finding minimum spanning trees. Inf. Process. Lett. 4(3), 53–57 (1975)
Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1–13 (1977)
Jones, D.W.: An empirical comparison of priority-queue and event-set implementations. Commun. ACM 29(4), 300–311 (1986)
Kaldewaij, A., Schoenmakers, B.: The derivation of a tighter bound for top-down skew heaps. Inf. Process. Lett. 37(5), 265–271 (1991)
Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and boolean union-find. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 573–582. ACM (2002)
Kaplan, H., Tarjan, R.E.: New heap data structures. Tech. Rep. TR-597-99, Department of Computer Science, Princeton University (1999)
Kaplan, H., Tarjan, R.E.: Thin heaps, thick heaps. ACM Trans. Algorithms 4(1) (2008)
Kaplan, H., Zwick, U.: A simpler implementation and analysis of chazelle’s soft heaps. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 477–485. SIAM (2009)
Khoong, C.M., Leong, H.W.: Double-ended binomial queues. In: Ng, K.W., Balasubramanian, N.V., Raghavan, P., Chin, F.Y.L. (eds.) ISAAC 1993. LNCS, vol. 762, pp. 128–137. Springer, Heidelberg (1993)
Kumar, V., Schwabe, E.J.: Improved algorithms and data structures for solving graph problems in external memory. In: Proc. 8th Symposium on Parallel and Distributed Processing, pp. 169–177. IEEE (1996)
LaMarca, A., Ladner, R.E.: The influence of caches on the performance of heaps. ACM J. Experimental Algorithmics 1, 4 (1996)
van Leeuwen, J., Wood, D.: Interval heaps. Comput. J. 36(3), 209–216 (1993)
Mendelson, R., Tarjan, R.E., Thorup, M., Zwick, U.: Melding priority queues. ACM Trans. Algorithms 2(4), 535–556 (2006)
Munro, J.I.: An implicit data structure supporting insertion, deletion, and search in O(log2 n) time. J. Comput. Syst. Sci. 33(1), 66–74 (1986)
Munro, J.I., Paterson, M.: Selection and sorting with limited storage. Theoretical Computer Science 12, 315–323 (1980)
Munro, J.I., Poblete, P.V.: Searchability in merging and implicit data structures. BIT 27(3), 324–329 (1987)
Munro, J.I., Suwanda, H.: Implicit data structures for fast search and update. J. Comput. Syst. Sci. 21(2), 236–250 (1980)
Okasaki, C.: Alternatives to two classic data structures. In: Proc. 36th SIGCSE Technical Symposium on Computer Science Education, pp. 162–165. ACM (2005)
Olariu, S., Overstreet, C.M., Wen, Z.: A mergeable double-ended priority queue. Comput. J. 34(5), 423–427 (1991)
Pagter, J., Rauhe, T.: Optimal time-space trade-offs for sorting. In: Proc. 39th Foundations of Computer Science, pp. 264–268. IEEE (1998)
Peterson, G.L.: A balanced tree scheme for meldable heaps with updates. Tech. Rep. GIT-ICS-87-23, School of Informatics and Computer Science, Georgia Institute of Technology (1987)
Pettie, S.: Towards a final analysis of pairing heaps. In: Proc. 46th Foundations of Computer Science, pp. 174–183. IEEE (2005)
Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16–34 (2002)
Porter, T., Simon, I.: Random insertion into a priority queue structure. IEEE Trans. Software Eng. 1(3), 292–298 (1975)
Raman, R.: Priority queues: Small, monotone and trans-dichotomous. In: Díaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 121–137. Springer, Heidelberg (1996)
Sack, J.R., Strothotte, T.: An algorithm for merging heaps. Acta Inf. 22(2), 171–186 (1985)
Sanders, P.: Fast priority queues for cached memory. ACM J. Experimental Algorithmics 5, 7 (2000)
Schoenmakers, B.: A tight lower bound for top-down skew heaps. Inf. Process. Lett. 61(5), 279–284 (1997)
Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652–686 (1985)
Sleator, D.D., Tarjan, R.E.: Self-adjusting heaps. SIAM J. Comput. 15(1), 52–69 (1986)
Stasko, J.T., Vitter, J.S.: Pairing heaps: experiments and analysis. Commun. ACM 30(3), 234–249 (1987)
Thorup, M.: Faster deterministic sorting and priority queues in linear space. In: Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 550–555. SIAM (1998)
Thorup, M.: On RAM priority queues. SIAM J. Comput. 30(1), 86–109 (2000)
Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. 69(3), 330–353 (2004)
Thorup, M.: Equivalence between priority queues and sorting. J. ACM 54(6) (2007)
Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4), 309–315 (1978)
Willard, D.E.: Log-logarithmic worst-case range queries are possible in space Θ(N). Inf. Process. Lett. 17(2), 81–84 (1983)
Williams, J.W.J.: Algorithm 232: Heapsort. Commun. ACM 7(6), 347–348 (1964)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Brodal, G.S. (2013). A Survey on Priority Queues. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds) Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science, vol 8066. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40273-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-40273-9_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40272-2
Online ISBN: 978-3-642-40273-9
eBook Packages: Computer ScienceComputer Science (R0)