Abstract
This paper introduces a highly efficient double-ended heap structure called d-b-queues, which are an extension of binomial queues. D-b-queues achieve the following amortized time bounds: O(1) for findmin, findmax, insert, and merge operations, and O(logn) for deletemin, deletemax, decreasekey, increasekey, arbitrary delete, and split operations. An n-node d-b-queue can be constructed in 1.75n comparisons. Our results include a simple proof of O(1) amortized time merging for ordinary binomial queues.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. D. Atkinson, J.-R. Sack, N. Santoro, and T. Strothotte, Min-max heaps and generalized priority queues. Comm. ACM 29 (1986) 996–1000.
S. Carlsson, The deap — A double-ended heap to implement double-ended priority queues. Inform. Proc. Lett. 26 (1987) 33–36.
G. Gambosi, E. Nardelli, and M. Talamo, A pointer-free data structure for merging heaps and min-max heaps. Theoret. Comput. Sci. 84 (1991) 107–126.
C. M. Khoong, The design and analysis of heap algorithms. M.Sc. Thesis, Department of Information Systems and Computer Science, National University of Singapore, Singapore, 1993.
C. M. Khoong and H. W. Leong, Relaxed inorder heaps. Submitted for publication.
S. Olariu, C. M. Overstreet, and Z. Wen (1991), A mergeable doubleended priority queue. Computer J., Vol. 34, pp. 423–427.
J. Vuillemin, A data structure for manipulating priority queues. Comm. ACM 21 (1978)309–315.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khoong, C.M., Leong, H.W. (1993). Double-ended binomial queues. 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_242
Download citation
DOI: https://doi.org/10.1007/3-540-57568-5_242
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