Abstract
Priority queues and double-ended priority queues are fundamental data types in computer science. Several implicit data structures have been proposed for implementing the queues, such as heaps, min-max heaps, deaps, and twin-heaps. Over the years the problem of constructing these heap-like structures has received much attention in the literature, but different structures possess different construction algorithms. In this paper, we present a uniform approach for building the heap-like data structures in-place. The study is carried out by investigating hardest instances of the problem and developing an algorithmic paradigm for the construction. Our paradigm produces comparison- and space-efficient construction algorithms for the heaplike structures, which improve over those previously fast known algorithms.
Part of the work was conducted while the author was with Lund University, Sweden.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopocroft, and J. D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts, 1974.
M. D. Atkinson, J.-R. Sack, N. Santoro, and Th. Strothotte: Min-max heaps and generalized priority queues. CACM 29 (10) (1986), 996–1000.
S. Carlsson: A variant of heapsort with almost optimal number of comparisons. Information Processing Letters 24 (4) (1987), 247–250.
S. Carlsson: Average-case results on heapsort. BIT 27 (1) (1987), 2–17.
S. Carlsson: The deap — A double-ended heap to implement double-ended priority queues. Information Processing Letters 26 (1) (1987), 33–36.
L. Draws, P. Eriksson, E. Forslund, L. Höglund, S. Vallner, and Th. Strothotte: Two new algorithms for constructing min-max heaps. In: Proce. 1st SWAT (1988), 43–50.
H. Erkiö: On heapsort and its dependence on input data. Technical Report A-1979-1. Department of Computer Science, University of Helsinki, Finland, 1979.
R. W. Floyd: Algorithm 245 — Treesort 3. CACM 7 (12) (1964), 701.
G. H. Gonnet and J. I. Munro: Heaps on heaps. SIAM J. Comput. 15 (1986), 964–971.
A. Hasham and J.-R. Sack: Bounds for min-max heaps. BIT 27 (3) (1987), 315–323.
D. B. Johnson: Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24 (1) (1979), 1–13.
D. E. Knuth: The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Massachusetts, 1973.
S. Okoma: Generalized heapsort. In: Proce. 9 th MFCS (1980), 439–451.
A. Schönhage, M. Paterson, and N. Pippenger: Finding the median. Journal of Computer and System Sciences 13 (2) (1976), 184–199.
Th. Strothotte, P. Eriksson, and S. Vallner: A note on constructing min-max heaps. BIT 29 (2) (1989), 251–256.
J. Vuillemin: A data structure for manipulating priority queues. CACM 21 (1978), 309–314.
J. W. J. Williams: Algorithm 232: Heapsort. CACM 7 (6) (1964), 347–348.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, J. (1993). A framework for constructing heap-like structures in-place. In: Ng, K.W., Raghavan, P., Balasubramanian, N.V., Chin, F.Y.L. (eds) Algorithms and Computation. ISAAC 1993. Lecture Notes in Computer Science, vol 762. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57568-5_241
Download citation
DOI: https://doi.org/10.1007/3-540-57568-5_241
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57568-9
Online ISBN: 978-3-540-48233-8
eBook Packages: Springer Book Archive