论文标题
软序列堆
Soft Sequence Heaps
论文作者
论文摘要
Chazelle [JACM00]引入了软堆，作为有效的最小树算法的组成部分，最近Kaplan等人。 [SOSA2019]展示了如何应用软堆来实现各种选择问题的简单算法。通过允许$ n $插入后损坏的$εn$损坏的$εn$通过损坏的$εn$，其中损坏的物品是具有人为增加的密钥，而$ 0 <ε\ leq 1/2 $是固定错误参数。 Chazelle的软堆基于二项式树，并在摊销的$ O（\ lg（1/ε））$时间内进行支持插入，并在摊销的$ O（1）$ time中提取米（trice-min）操作。 在本文中，我们探讨了软堆的设计空间。本文的主要贡献是基于合并排序序列的替代软堆实现，与Chazelle软堆相匹配的时间界。我们还讨论了Kaplan等人的软堆的变化。 [sicomp2013]，我们避免懒惰地进行插入。它基于三元树而不是二进制树，并匹配Kaplan等人的时间范围，即摊销$ O（1）$插入和摊销$ O（\ lg（1/ε））$提取物。我们的两种数据结构仅在提取最终操作后引入损坏，这些操作返回了操作破坏的项目集。
Chazelle [JACM00] introduced the soft heap as a building block for efficient minimum spanning tree algorithms, and recently Kaplan et al. [SOSA2019] showed how soft heaps can be applied to achieve simpler algorithms for various selection problems. A soft heap trades-off accuracy for efficiency, by allowing $εN$ of the items in a heap to be corrupted after a total of $N$ insertions, where a corrupted item is an item with artificially increased key and $0 < ε\leq 1/2$ is a fixed error parameter. Chazelle's soft heaps are based on binomial trees and support insertions in amortized $O(\lg(1/ε))$ time and extract-min operations in amortized $O(1)$ time. In this paper we explore the design space of soft heaps. The main contribution of this paper is an alternative soft heap implementation based on merging sorted sequences, with time bounds matching those of Chazelle's soft heaps. We also discuss a variation of the soft heap by Kaplan et al. [SICOMP2013], where we avoid performing insertions lazily. It is based on ternary trees instead of binary trees and matches the time bounds of Kaplan et al., i.e. amortized $O(1)$ insertions and amortized $O(\lg(1/ε))$ extract-min. Both our data structures only introduce corruptions after extract-min operations which return the set of items corrupted by the operation.
