Abstract
We introduce an adaptation of run-relaxed heaps which provides efficient heap operations with respect to the number of element comparisons performed. Our data structure guarantees the worst-case cost of O(1) for find–min, insert, and decrease; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for delete, improving the bound of \(3\lg n + O(1)\) on the number of element comparisons known for run-relaxed heaps. Here, n denotes the number of elements stored prior to the operation in question, and lg n equals max{1, log2 n}.
Partially supported by the Danish Natural Science Research Council under contracts 21-02-0501 (project Practical data structures and algorithms) and 272-05-0272 (project Generic programming—algorithms and tools).
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
Brodal, G.S.: Worst-case efficient priority queues. In: Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58. ACM/SIAM (1996)
Clancy, M.J., Knuth, D.E.: A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Science, Stanford University (1977)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM 31, 1343–1354 (1988)
Elmasry, A.: Layered heaps. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 212–222. Springer, Heidelberg (2004)
Elmasry, A., Jensen, C., Katajainen, J.: A framework for speeding up priority-queue operations. CPH STL Report 2004-3. Department of Computing, University of Copenhagen (2004), available at http://cphstl.dk
Elmasry, A., Jensen, C., Katajainen, J.: Multipartite priority queues (2004) (submitted for publication)
Fredman, M.L.: On the efficiency of pairing heaps and related data structures. Journal of the ACM 46, 473–501 (1999)
Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: A new form of self-adjusting heap. Algorithmica 1, 111–129 (1986)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34, 596–615 (1987)
Gonnet, G.H., Munro, J.I.: Heaps on heaps. SIAM Journal on Computing 15, 964–971 (1986)
Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and Boolean union-find. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 573–582. ACM Press, New York (2002)
Kaplan, H., Tarjan, R.E.: New heap data structures. Technical Report TR-597-99, Department of Computer Science, Princeton University (1999)
Okasaki, C.: Purely Functional Data Structures. Cambridge University Press, Cambridge (1998)
Overmars, M.H., van Leeuwen, J.: Worst-case optimal insertion and deletion methods for decomposable searching problems. Information Processing Letters 12, 168–173 (1981)
Vuillemin, J.: A data structure for manipulating priority queues. Communications of the ACM 21, 309–315 (1978)
Williams, J.W.J.: Algorithm 232: Heapsort. Communications of the ACM 7, 347–348 (1964)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Elmasry, A., Jensen, C., Katajainen, J. (2006). Two-Tier Relaxed Heaps. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_32
Download citation
DOI: https://doi.org/10.1007/11940128_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)