| dbo:abstract
|
- A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986.Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations (assuming a min-heap):
* find-min: simply return the top element of the heap.
* meld: compare the two root elements, the smaller remains the root of the result, the larger element and its subtree is appended as a child of this root.
* insert: create a new heap for the inserted element and meld into the original heap.
* decrease-key (optional): remove the subtree rooted at the key to be decreased, replace the key with a smaller key, then meld the result back into the heap.
* delete-min: remove the root and do repeated melds of its subtrees until one tree remains. Various merging strategies are employed. The analysis of pairing heaps' time complexity was initially inspired by that of splay trees.The amortized time per delete-min is O(log n), and the operations find-min, meld, and insert run in O(1) amortized time. When a decrease-key operation is added as well, determining the precise asymptotic running time of pairing heaps has turned out to be difficult. Initially, the time complexity of this operation was conjectured on empirical grounds to be O(1), but Fredman proved that the amortized time per decrease-key is at least for some sequences of operations.Using a different amortization argument, Pettie then proved that insert, meld, and decrease-key all run in amortized time, which is .Elmasry later introduced elaborations of pairing heaps (lazy, consolidate) for which decrease-key runs in amortized time and other operations have optimal amortized bounds, but no tight bound is known for the original data structure. Although the asymptotic performance of pairing heaps is worse than other priority queue algorithms such as Fibonacci heaps, which perform decrease-key in amortized time, the performance in practice is excellent. Jonesand Larkin, Sen, and Tarjanconducted experiments on pairing heaps and other heap data structures. They concluded that d-ary heaps such as binary heaps are faster than all other heap implementations when the decrease-key operation is not needed (and hence there is no need to externally track the location of nodes in the heap), but that when decrease-key is needed pairing heaps are often faster than d-ary heaps and almost always faster than other pointer-based heaps, including data structures like Fibonacci heaps that are theoretically more efficient. Chen et al. examined priority queues specifically for use with Dijkstra's algorithm and concluded that in normal cases using a d-ary heap without decrease-key (instead duplicating nodes on the heap and ignoring redundant instances) resulted in better performance, despite the inferior theoretical performance guarantees. (en)
- 配对堆是一种实现简单、均摊复杂度优越的堆数据结构，由、罗伯特·塞奇威克、、羅伯特·塔揚于1986年发明。配对堆是一种多叉树，并且可以被认为是一种简化的斐波那契堆。对于实现例如普林姆最小生成树算法等算法，配对堆是一个更优的选择，且支持以下操作（假设该堆是最小堆）：
* find-min（查找最小值）：返回堆顶。
* merge（合并）：比较两个堆顶，将堆顶较大的堆设为另一个的孩子。
* insert（插入）：创建一个只有一个元素的堆，并合并至原堆中。
* decrease-key（减小元素）（可选）：将以该节点为根的子树移除，减小其权值，并合并回去。
* delete-min（删除最小值）：删除根并将其子树合并至一起。这里有各种不同的方式。 配对堆时间复杂度的分析灵感来源于伸展树。其delete-min操作的时间复杂度为O(log n)，而find-min、merge和insert操作的均摊时间复杂度均为O(1)。 确定配对堆每次进行decrease-key操作的均摊时间复杂度是困难的。最初，基于经验，这个操作的时间复杂度被推测为是O(1)，但证明了对于某些操作序列，每次decrease-key操作的时间复杂度至少为。在那之后，通过不同的均摊依据，Pettie证明了insert、merge及decrease-key操作的均摊时间复杂度均为，近似于。Elmasry后来介绍了一种配对堆的变体，令其拥有所有斐波那契堆可以实现的操作，且decrease-key操作的均摊时间复杂度为，但对于原始的数据结构，仍未知准确的运行下限。此外，能否使delete-min在均摊时间复杂度为的同时，令insert操作的均摊时间复杂度为，目前也仍未得到解决。 尽管这比其他的，例如能实现均摊时间的decrease-key的斐波那契堆，这样的优先队列算法更差，在实践中配对堆的表现仍然很不错。和，Moret和Shapiro，以及Larkin、Sen和Tarjan进行过配对堆和其他堆数据结构的实验。 他们得出的结论是, 配对堆通常比基于数组的二叉堆和的实际操作速度更快，而且在实践中几乎总是比其他基于指针的堆更快，其中包括诸如斐波纳契堆这样的理论上更有效率的数据结构。 (zh)
|
| rdfs:comment
|
- A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986.Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations (assuming a min-heap): (en)
- 配对堆是一种实现简单、均摊复杂度优越的堆数据结构，由、罗伯特·塞奇威克、、羅伯特·塔揚于1986年发明。配对堆是一种多叉树，并且可以被认为是一种简化的斐波那契堆。对于实现例如普林姆最小生成树算法等算法，配对堆是一个更优的选择，且支持以下操作（假设该堆是最小堆）：
* find-min（查找最小值）：返回堆顶。
* merge（合并）：比较两个堆顶，将堆顶较大的堆设为另一个的孩子。
* insert（插入）：创建一个只有一个元素的堆，并合并至原堆中。
* decrease-key（减小元素）（可选）：将以该节点为根的子树移除，减小其权值，并合并回去。
* delete-min（删除最小值）：删除根并将其子树合并至一起。这里有各种不同的方式。 配对堆时间复杂度的分析灵感来源于伸展树。其delete-min操作的时间复杂度为O(log n)，而find-min、merge和insert操作的均摊时间复杂度均为O(1)。 (zh)
|
