nach oben

Theory of Computing Systems

Erschienen in:

21.04.2017

Optimizing Binary Heaps

verfasst von: Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen

Erschienen in: Theory of Computing Systems | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Excerpt

In its elementary form, a priority queue is a data structure that stores a multiset of elements and supports the operations: construct, minimum, insert, and extract-min [11, Chapter 6]. In most cases, in applications where this set of operations is sufficient, the basic priority queue that the users would select is a binary heap [49]. Even though a binary heap is practically efficient, its theoretical behaviour is known not to be optimal. The same is true for the best-known variants presented in the literature (see, e.g. [27]). …

Vorheriger Artikel Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts

Nächster Artikel On Compiling Structured CNFs to OBDDs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

As is standard, throughout the text, for integers d ≥ 2 and n ≥ 0, we write log d n when we mean log d(max{d,n}), and we use lg n as a shorthand for log 2n.

log ∗n is the iterated logarithm of n, recursively defined as 1 for n ≤ 2, and 1 + log ∗(lg n) for n > 2.

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)MathSciNetCrossRefMATH

Bollobás, B., Fenner, T., Frieze, A.: On the best case of heapsort. J. Algorithms 20(2), 205–217 (1996)MathSciNetCrossRefMATH

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)

Brown, M. R.: Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7(3), 298–319 (1978)MathSciNetCrossRefMATH

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)

Carlsson, S.: A variant of Heapsort with almost optimal number of comparisons. Inform. Process. Lett. 24(4), 247–250 (1987)MathSciNetCrossRefMATH

Carlsson, S.: An optimal algorithm for deleting the root of a heap. Inform. Process. Lett. 37(2), 117–120 (1991)MathSciNetCrossRefMATH

Carlsson, S., Chen, J., Mattsson, C.: Heaps with bits. Theoret. Comput. Sci. 164(1-2), 1–12 (1996)MathSciNetCrossRefMATH

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)

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)

11.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, 3th edn. The MIT Press, Cambridge (2009)MATH

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)

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)MathSciNetCrossRef

14.

Dutton, R. D.: Weak-heap sort. BIT 33(3), 372–381 (1993)MathSciNetCrossRef

15.

Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap data structure: Variants and applications. J. Discrete Algorithms 16, 187–205 (2012)MathSciNetCrossRefMATH

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)

17.

Edelkamp, S., Elmasry, A., Katajainen, J.: Weak heaps engineered. J. Discrete Algorithms 23, 83–97 (2013)MathSciNetCrossRefMATH

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)

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)

20.

Elmasry, A., Jensen, C., Katajainen, J.: Multipartite priority queues. ACM Trans. Algorithms 5(1), 14:1–14:19 (2008)MathSciNetCrossRefMATH

21.

Elmasry, A., Jensen, C., Katajainen, J.: Two skew-binary numeral systems and one application. Theory Comput. Syst. 50(1), 185–211 (2012)MathSciNetCrossRefMATH

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)

24.

Fleischer, R.: A tight lower bound for the worst case of Bottom-up-heapsort. Algorithmica 11(2), 104–115 (1994)MathSciNetCrossRef

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)MathSciNetCrossRefMATH

26.

Floyd, R. W.: Algorithm 245: Treesort 3. Commun. ACM 7(12), 701 (1964)CrossRef

27.

Gonnet, G. H., Munro, J. I.: Heaps on heaps. SIAM J. Comput. 15(4), 964–971 (1986)MathSciNetCrossRefMATH

28.

Han, Y.: Deterministic sorting in O(n log log n) time and linear space. J. Algorithms 50(1), 96–105 (2004)MathSciNetCrossRefMATH

29.

Han, Y., Thorup, M.: Integer sorting in \({O}(n \sqrt {\log \log n})\) expected time and linear space FOCS 2002, pp 135–144. IEEE Computer Society, Los Alamitos (2002)

30.

Harvey, N. J. A., Zatloukal, K. C.: The Post-Order Heap FUN 2004 (2004)

31.

Hayward, R., McDiarmid, C.: Average case analysis of heap building by repeated insertion. J. Algorithms 12(1), 126–153 (1991)MathSciNetCrossRefMATH

32.

Johnson, D. B.: Priority queues with update and finding minimum spanning trees. Inform. Process. Lett. 4(3), 53–57 (1975)CrossRefMATH

33.

Katajainen, J.: The Ultimate Heapsort CATS 1998, Australian computer science communications, vol. 20, pp 87–95. Springer, Singapore (1998)

34.

Knuth, D. E. The Art of Computer Programming: Fundamental Algorithms, 3rd edn, vol. 1. Addison Wesley Longman, Reading (1997)

35.

Knuth, D. E. The Art of Computer Programming: Sorting and Searching, 2nd edn, vol. 3. Addison Wesley Longman, Reading (1998)

36.

Levcopoulos, C., Petersson, O.: Adaptive heapsort. J. Algorithms 14(3), 395–413 (1993)MathSciNetCrossRefMATH

37.

McDiarmid, C. J. H., Reed, B. A.: Building heaps fast. J. Algorithms 10 (3), 352–365 (1989)MathSciNetCrossRefMATH

38.

Nievergelt, J., Reingold, E.: Binary search trees of bounded balance. SIAM J. Comput. 2(1), 33–43 (1973)MathSciNetCrossRefMATH

39.

Overmars, M. H.: The Design of Dynamic Data Structures, LNCS, vol. 156. Springer, Heidelberg (1983)

40.

Sack, J. R., Strothotte, T.: A characterization of heaps and its applications 86(1), 69–86 (1990)

41.

Schaffer, R., Sedgewick, R.: The analysis of heapsort. J. Algorithms 15(1), 76–100 (1993)MathSciNetCrossRefMATH

42.

Suchenek, M. A.: Elementary yet precise worst-case analysis of Floyd’s heap-construction program. Fund. Inform. 120(1), 75–92 (2012)MathSciNetMATH

43.

Thorup, M.: Equivalence between priority queues and sorting. J. ACM 54(6), 28:1–28:27 (2007)MathSciNetCrossRefMATH

44.

Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4), 309–315 (1978)MathSciNetCrossRefMATH

45.

Wang, X., Wu, Y., Zhu, D.: A new variant of in-place sort algorithm. Procedia Eng. 29, 2274–2278 (2012)CrossRef

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)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

48.

Wegener, I.: A simple modification of Xunrang and Yuzhang’s Heapsort variant improving its complexity significantly. Comput. J. 36(3), 286–288 (1993)CrossRefMATH

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)CrossRef

51.

Xunrang, G., Yuzhang, Z.: Asymptotic optimal Heapsort algorithm. Theoret. Comput. Sci. 134(2), 559–565 (1994)MathSciNetCrossRefMATH

52.

Xunrang, G., Yuzhang, Z.: Optimal heapsort algorithm. Theoret. Comput. Sci. 163(1–2), 239–243 (1996)MathSciNetCrossRefMATH

Titel: Optimizing Binary Heaps
verfasst von: Stefan Edelkamp
Amr Elmasry
Jyrki Katajainen
Publikationsdatum: 21.04.2017
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-017-9760-2

Springer Professional

Excerpt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2017

Guest Editorial: Computer Science Symposium in Russia

The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

On Compiling Structured CNFs to OBDDs

The Query Complexity of Witness Finding

Satisfiability of ECTL∗ with Local Tree Constraints

Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts

Premium Partner