论文标题
一个更简单的证据，即配对堆占用o（1）每插入时间的摊销时间
A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion
论文作者
论文摘要
配对堆是一个简单的“自我调整”实现（优先队列）。将项目插入配对堆中或减少项目的钥匙需要O（1）时间最差的案例，融合了两个堆。但是，在最坏情况下，删除最小键的项目可能需要在堆大小的情况下进行线性线性。引入配对堆的论文证明了每个堆操作的o（log n）摊销时间，其中n是操作中堆或堆中的项目数量，通过向每个删除的所有时间（log n）除非将所有删除的时间（log n）用于非删除操作，o（log n）的所有时间，o（log n log n）。后来，Iacono找到了一种方法，将每插入的摊销时间减少到O（1），而将MELD的摊销时间缩短为零，同时保留了其他更新操作的O（log n）摊销时间。我们为IACONO的结果提供了更简单的证明，其恒定因素明显较小。我们的分析使用配对堆的自然表示，而不是将原始分析和IACONO中使用的二进制树转化为二进制树。
The pairing heap is a simple "self-adjusting" implementation of a heap (priority queue). Inserting an item into a pairing heap or decreasing the key of an item takes O(1) time worst-case, as does melding two heaps. But deleting an item of minimum key can take time linear in the heap size in the worst case. The paper that introduced the pairing heap proved an O(log n) amortized time bound for each heap operation, where n is the number of items in the heap or heaps involved in the operation, by charging all but O(log n) of the time for each deletion to non-deletion operations, O(log n) to each. Later Iacono found a way to reduce the amortized time per insertion to O(1) and that of meld to zero while preserving the O(log n) amortized time bound for the other update operations. We give a simpler proof of Iacono's result with significantly smaller constant factors. Our analysis uses the natural representation of pairing heaps instead of the conversion to a binary tree used in the original analysis and in Iacono's.
