Abstract
A lower bound is presented which shows that a class of heap algorithms in the pointer model with only heap pointers must spend \(\Omega \left( \frac{\log \log n}{\log \log \log n} \right)\) amortized time on the Decrease-Key operation (given O(logn) amortized-time Extract-Min). Intuitively, this bound shows the key to having O(1)-time Decrease-Key is the ability to sort O(logn) items in O(logn) time; Fibonacci heaps [M. .L. Fredman and R. E. Tarjan. J. ACM 34(3):596-615 (1987)] do this through the use of bucket sort. Our lower bound also holds no matter how much data is augmented; this is in contrast to the lower bound of Fredman [J. ACM 46(4):473-501 (1999)] who showed a tradeoff between the number of augmented bits and the amortized cost of Decrease-Key. A new heap data structure, the sort heap, is presented. This heap is a simplification of the heap of Elmasry [SODA 2009: 471-476] and shares with it a O(loglogn) amortized-time Decrease-Key, but with a straightforward implementation such that our lower bound holds. Thus a natural model is presented for a pointer-based heap such that the amortized runtime of a self-adjusting structure and amortized lower asymptotic bounds for Decrease-Key differ by but a O(logloglogn) factor.
The full version is on the arXiv at CoRR abs/1302.6641 (2013).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Elmasry, A.: Pairing heaps with O(log log n) decrease cost. In: SODA, pp. 471–476 (2009)
Elmasry, A.: Pairing Heaps with Costless Meld. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 183–193. Springer, Heidelberg (2010)
Fredman, M.L.: A Priority Queue Transform. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol. 1668, pp. 244–258. Springer, Heidelberg (1999)
Fredman, M.L.: On the Efficiency of Pairing Heaps and Related Data Structures. J. ACM 46(4), 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(1), 111–129 (1986)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)
Iacono, J.: Improved Upper Bounds for Pairing Heaps. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 32–45. Springer, Heidelberg (2000)
Pettie, S.: Towards a Final Analysis of Pairing Heaps. In: FOCS, pp. 174–183 (2005)
Sleator, D.D., Tarjan, R.E.: Self-Adjusting Binary Search Trees. J. ACM 32(3), 652–686 (1985)
Sleator, D.D., Tarjan, R.E.: Self-Adjusting Heaps. SIAM J. Comput. 15(1), 52–69 (1986)
Stasko, J.T., Vitter, J.S.: Pairing Heaps: Experiments and Analysis. Commun. ACM 30(3), 234–249 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Iacono, J., Özkan, Ö. (2014). Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_53
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)