×

Optimizing binary heaps. (English) Zbl 1378.68030

Summary: A priority queue – a data structure supporting, inter alia, the operations minimum (top), insert (push), and extract-min (pop) – is said to operate in-place if it uses \(O(1)\) extra space in addition to the n elements stored at the beginning of an array. Prior to this work, no in-place priority queue was known to provide worst-caseguarantees on the number of element comparisons that are optimal up to additive constant terms for both insert and extract-min. In particular, for the standard implementation of binary heaps, insert and extract-min operate in logarithmic time while involving at most \(\lceil \lg n\rceil\) and \(2 \lg n\) [could possibly be reduced to \(\lg \lg n + O(1)\) and \(\lg n + \log^\ast n + O(1)\)] element comparisons, respectively. In this paper we propose a variant of a binary heap that operates in-place, executes minimum and insert in \(O(1)\) worst-case time, and extract-min in \(O(\lg n)\) worst-case time while involving at most \(\lg n + O(1)\) element comparisons. These efficiencies surpass lower bounds known for binary heaps, thereby resolving a long-standing theoretical debate.

MSC:

68P05 Data structures

Software:

heapsort
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alstrup, S., Husfeldt, T., Rauhe, T., Thorup, M.: Black box for constant-time insertion in priority queues. ACM Trans. Algorithms 1(1), 102-106 (2005) · Zbl 1321.68232 · doi:10.1145/1077464.1077471
[2] Bollobás, B., Fenner, T., Frieze, A.: On the best case of heapsort. J. Algorithms 20(2), 205-217 (1996) · Zbl 0843.68035 · doi:10.1006/jagm.1996.0011
[3] Brodal, G. S., Nielsen, J. S., Truelsen, J.: Strictly implicit priority queues: on the number of moves and worst-case time WADS 2015, vol. 9214, pp 91-102. Springer, Heidelberg (2015) · Zbl 1444.68055
[4] Brown, M. R.: Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7(3), 298-319 (1978) · Zbl 0379.68023 · doi:10.1137/0207026
[5] Bruun, A., Edelkamp, S., Katajainen, J., Rasmussen, J.: Policy-based benchmarking of weak heaps and their relatives SEA 2010, LNCS, vol. 6049, pp 424-435. Springer, Heidelberg (2010) · Zbl 1252.68090
[6] Carlsson, S.: A variant of Heapsort with almost optimal number of comparisons. Inform. Process. Lett. 24(4), 247-250 (1987) · Zbl 0653.68051 · doi:10.1016/0020-0190(87)90142-6
[7] Carlsson, S.: An optimal algorithm for deleting the root of a heap. Inform. Process. Lett. 37(2), 117-120 (1991) · Zbl 0713.68018 · doi:10.1016/0020-0190(91)90144-7
[8] Carlsson, S., Chen, J., Mattsson, C.: Heaps with bits. Theoret. Comput. Sci. 164(1-2), 1-12 (1996) · Zbl 0874.68084 · doi:10.1016/0304-3975(95)00152-2
[9] Carlsson, S., Munro, J. I., Poblete, P. V.: An implicit binomial queue with constant insertion time SWAT 1988, LNCS, vol. 318, pp 1-13. Springer, Heidelberg (1988) · Zbl 0651.68037
[10] Chen, J., Edelkamp, S., Elmasry, A., Katajainen, J.: In-Place heap construction with optimized comparisons, moves, and cache misses MFCS 2012, LNCS, vol. 7464, pp 259-270. Springer, Heidelberg (2012) · Zbl 1365.68177
[11] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, 3th edn. The MIT Press, Cambridge (2009) · Zbl 1187.68679
[12] Darwish, O., Elmasry, A., Katajainen, J.: Memory-adjustable navigation piles with applications to sorting and convex hulls. E-print arXiv:1510.07185, arXiv.org Ithaca (2015) · Zbl 07475097
[13] 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) · doi:10.1145/50087.50096
[14] Dutton, R. D.: Weak-heap sort. BIT 33(3), 372-381 (1993) · Zbl 1408.68043 · doi:10.1007/BF01990520
[15] Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap data structure: Variants and applications. J. Discrete Algorithms 16, 187-205 (2012) · Zbl 1257.68059 · doi:10.1016/j.jda.2012.04.010
[16] Edelkamp, S., Elmasry, A., Katajainen, J.: A catalogue of weak-heap programs. CPH STL Report 2012-2. Dept. Comput. Sci., Univ, Copenhagen, Copenhagen (2012) · Zbl 1293.68085
[17] Edelkamp, S., Elmasry, A., Katajainen, J.: Weak heaps engineered. J. Discrete Algorithms 23, 83-97 (2013) · Zbl 1334.68051 · doi:10.1016/j.jda.2013.07.002
[18] Edelkamp, S., Elmasry, A., Katajainen, J.: Strengthened lazy heaps: Surpassing the lower bounds for binary heaps. E-print arXiv:1407.3377, arXiv.org Ithaca (2014) · Zbl 0785.68045
[19] Edelkamp, S., Elmasry, A., Katajainen, J.: An in-place Priority Queue with O(1) Time for Push and lg n + O(1) Comparisons for Pop CSR 2015, LNCS, vol. 9139, pp 1-15. Springer, Heidelberg (2015) · Zbl 1465.68058
[20] Elmasry, A., Jensen, C., Katajainen, J.: Multipartite priority queues. ACM Trans. Algorithms 5(1), 14:1-14:19 (2008) · Zbl 1183.68213 · doi:10.1145/1435375.1435389
[21] Elmasry, A., Jensen, C., Katajainen, J.: Two skew-binary numeral systems and one application. Theory Comput. Syst. 50(1), 185-211 (2012) · Zbl 1254.68097 · doi:10.1007/s00224-011-9357-0
[22] Elmasry, A., Katajainen, J.: Towards ultimate binary heaps CPH STL report 2013-1. Dept. Comput. Sci., Univ, Copenhagen, Copenhagen (2013)
[23] van Emde Boas, P.: Thirty nine years of stratified trees ISCIM 2013, vol. 1, pp 1-14. Epoka University, Tirana (2013) · Zbl 0770.68075
[24] Fleischer, R.: A tight lower bound for the worst case of Bottom-up-heapsort. Algorithmica 11(2), 104-115 (1994) · doi:10.1007/BF01182770
[25] Fleischer, R., Sinha, B., Uhrig, C.: A lower bound for the worst case of Bottom-up-heapsort. Inform. and Comput. 102(3), 263-279 (1993) · Zbl 0785.68045 · doi:10.1006/inco.1993.1009
[26] Floyd, R. W.: Algorithm 245: Treesort 3. Commun. ACM 7(12), 701 (1964) · doi:10.1145/355588.365103
[27] Gonnet, G. H., Munro, J. I.: Heaps on heaps. SIAM J. Comput. 15(4), 964-971 (1986) · Zbl 0619.68042 · doi:10.1137/0215068
[28] Han, Y.: Deterministic sorting in O(n log log n) time and linear space. J. Algorithms 50(1), 96-105 (2004) · Zbl 1106.68028 · doi:10.1016/j.jalgor.2003.09.001
[29] Han, Y.; Thorup, M., Integer sorting in \({O}(n \sqrt{\log \log n})O\)(nlog logn) expected time and linear space, 135-144 (2002), Los Alamitos
[30] Harvey, NJA; Zatloukal, KC, The Post-Order Heap (2004)
[31] Hayward, R., McDiarmid, C.: Average case analysis of heap building by repeated insertion. J. Algorithms 12(1), 126-153 (1991) · Zbl 0715.68038 · doi:10.1016/0196-6774(91)90027-V
[32] Johnson, D. B.: Priority queues with update and finding minimum spanning trees. Inform. Process. Lett. 4(3), 53-57 (1975) · Zbl 0318.68032 · doi:10.1016/0020-0190(75)90001-0
[33] Katajainen, J.: The Ultimate Heapsort CATS 1998, Australian computer science communications, vol. 20, pp 87-95. Springer, Singapore (1998) · Zbl 0951.68506
[34] Knuth, D. E. The Art of Computer Programming: Fundamental Algorithms, 3rd edn, vol. 1. Addison Wesley Longman, Reading (1997) · Zbl 0895.68055
[35] Knuth, D. E. The Art of Computer Programming: Sorting and Searching, 2nd edn, vol. 3. Addison Wesley Longman, Reading (1998) · Zbl 0302.68010
[36] Levcopoulos, C., Petersson, O.: Adaptive heapsort. J. Algorithms 14(3), 395-413 (1993) · Zbl 0781.68045 · doi:10.1006/jagm.1993.1021
[37] McDiarmid, C. J. H., Reed, B. A.: Building heaps fast. J. Algorithms 10 (3), 352-365 (1989) · Zbl 0681.68069 · doi:10.1016/0196-6774(89)90033-3
[38] Nievergelt, J., Reingold, E.: Binary search trees of bounded balance. SIAM J. Comput. 2(1), 33-43 (1973) · Zbl 0262.68012 · doi:10.1137/0202005
[39] Overmars, M. H.: The Design of Dynamic Data Structures, LNCS, vol. 156. Springer, Heidelberg (1983) · Zbl 0545.68009
[40] Sack, J. R., Strothotte, T.: A characterization of heaps and its applications 86(1), 69-86 (1990) · Zbl 0705.68043
[41] Schaffer, R., Sedgewick, R.: The analysis of heapsort. J. Algorithms 15(1), 76-100 (1993) · Zbl 0789.68072 · doi:10.1006/jagm.1993.1031
[42] Suchenek, M. A.: Elementary yet precise worst-case analysis of Floyd’s heap-construction program. Fund. Inform. 120(1), 75-92 (2012) · Zbl 1252.68090
[43] Thorup, M.: Equivalence between priority queues and sorting. J. ACM 54(6), 28:1-28:27 (2007) · Zbl 1326.68113 · doi:10.1145/1314690.1314692
[44] Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4), 309-315 (1978) · Zbl 0371.68011 · doi:10.1145/359460.359478
[45] Wang, X., Wu, Y., Zhu, D.: A new variant of in-place sort algorithm. Procedia Eng. 29, 2274-2278 (2012) · doi:10.1016/j.proeng.2012.01.300
[46] Wegener, I.: The worst case complexity of McDiarmid and Reed’s variant of Bottom-up Heapsort is less than n log n + 1.1n. Inform. and Comput. 97(1), 86-96 (1992) · Zbl 0766.68025 · doi:10.1016/0890-5401(92)90005-Z
[47] Wegener, I.: Bottom-up-heapsort, a new variant of Heapsort beating, on an average, Quicksort (if n is not very small). Theoret. Comput. Sci. 118(1), 81-98 (1993) · Zbl 0783.68060 · doi:10.1016/0304-3975(93)90364-Y
[48] Wegener, I.: A simple modification of Xunrang and Yuzhang’s Heapsort variant improving its complexity significantly. Comput. J. 36(3), 286-288 (1993) · Zbl 0770.68075 · doi:10.1093/comjnl/36.3.286
[49] Williams, J. W. J.: Algorithm 232: Heapsort. Commun. ACM 7(6), 347-348 (1964)
[50] Xunrang, G., Yuzhang, Z.: A new Heapsort algorithm and the analysis of its complexity. Comput. J. 33(3), 281-282 (1990) · doi:10.1093/comjnl/33.3.281
[51] Xunrang, G., Yuzhang, Z.: Asymptotic optimal Heapsort algorithm. Theoret. Comput. Sci. 134(2), 559-565 (1994) · Zbl 0938.68959 · doi:10.1016/0304-3975(94)00113-8
[52] Xunrang, G., Yuzhang, Z.: Optimal heapsort algorithm. Theoret. Comput. Sci. 163(1-2), 239-243 (1996) · Zbl 0874.68083 · doi:10.1016/0304-3975(95)00233-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.