Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan [8], it has been an open question whether this or any other simple “self-adjusting” heap supports decrease-key operations in \(\mathrm{O}(\log\log n)\) time, where \(n\) is the number of heap items. Using powerful new techniques, we answer this question in the affirmative. We prove that both slim and smooth heaps, recently introduced self-adjusting heaps, support heap operations in the following amortized time bounds: \(\mathrm{O}(\log n)\) for delete-min and delete, \(\mathrm{O}(\log\log n)\) for decrease-key, and \(\mathrm{O}(1)\) for all other heap operations, including insert and meld, where \(n\) is the number of heap items that are eventually deleted: Items inserted but never deleted do not count in the bounds. We also analyze the multipass pairing heap, a variant of pairing heaps. For this heap implementation, we obtain the same bounds except for decrease-key, for which our bound is \(\mathrm{O}(\log\log n\cdot\log\log\log n)\) , where again items that are never deleted do not count in \(n\) . Our bounds significantly improve the best previously known bounds for all three data structures. For slim and smooth heaps our bounds are tight, since they match lower bounds of Iacono and Özkan [13].

Corwin Sinnamon

Robert E. Tarjan

ACM Transactions on Algorithms

ACM TRANSACTIONS ON ALGORITHMS 欢迎提交最高质量的原始研究，处理本质上离散和有限的算法，并且在目标或分析中以自然的方式具有数学内容。最受欢迎的是新算法和数据结构、新的和改进的分析以及复杂性结果。该杂志涵盖的具体计算领域包括组合搜索和对象；计数；离散优化和近似；随机化和量子计算；并行和分布式计算；图形算法、几何、算术、数论、字符串；在线分析；密码学；编码;数据压缩;学习算法;算法分析方法;离散算法应用于生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等应用领域

ACM Transactions on Algorithms welcomes submissions of high-quality original research that deals with discrete and finite algorithms, naturally incorporating mathematical content in its objectives or analyses. We particularly encourage new algorithms and data structures, novel and improved analyses, and complexity results. The specific computational areas covered by the journal include combinatorial search and objects, counting, discrete optimization and approximation, randomized and quantum computing, parallel and distributed computing, graph algorithms, geometry, arithmetic, number theory, string processing, online analysis, cryptography, coding, data compression, learning algorithms, algorithmic analysis methods, and the application of discrete algorithms in fields such as biology, economics, game theory, communications, computer systems and architecture, hardware design, and scientific computing.

《ACM Transactions on Algorithms》欢迎提交高质量的原创研究，主要涉及离散和有限算法，且在目标或分析中自然包含数学内容。我们特别欢迎新算法和数据结构的提出、新的和改进的分析方法，以及复杂性结果的研究。该期刊涵盖的具体计算领域包括组合搜索与对象、计数、离散优化与近似、随机化与量子计算、并行与分布式计算、图算法、几何、算术、数论、字符串处理、在线分析、密码学、编码、数据压缩、学习算法、算法分析方法，以及离散算法在生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等领域的应用。

Category	Quartile
计算机科学	3
计算机科学, 计算机理论方法	2
计算机科学, 应用数学	2

Efficiency of Self-Adjusting Heaps

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
MATHEMATICS, APPLIED	3