配对堆
![]() |
此条目翻译品质不佳。 |
配对堆 | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | 堆积 | ||||||||||||||||||||||||
发明时间 | 1986年 | ||||||||||||||||||||||||
发明者 | 迈克尔·弗雷德曼、罗伯特·塞奇威克、丹尼尔·斯莱托、罗伯特·塔扬 | ||||||||||||||||||||||||
用大O符号表示的时间复杂度 | |||||||||||||||||||||||||
|
配对堆(英语:Pairing heap)是一种实现简单、均摊复杂度优越的堆数据结构,由迈克尔·弗雷德曼、罗伯特·塞奇威克、丹尼尔·斯莱托、罗伯特·塔扬于1986年发明。[1] 配对堆是一种多叉树,并且可以被认为是一种简化的斐波那契堆。对于实现例如普林姆最小生成树算法等算法,配对堆是一个更优的选择[2],且支持以下操作(假设该堆是最小堆):
- find-min(查找最小值):返回堆顶。
- merge(合并):比较两个堆顶,将堆顶较大的堆设为另一个的孩子。
- insert(插入):创建一个只有一个元素的堆,并合并至原堆中。
- decrease-key(减小元素)(可选):将以该节点为根的子树移除,减小其权值,并合并回去。
- delete-min(删除最小值):删除根并将其子树合并至一起。这里有各种不同的方式。
配对堆时间复杂度的分析灵感来源于伸展树。[1] 其delete-min操作的时间复杂度为O(log n),而find-min、merge和insert操作的均摊时间复杂度均为O(1)。[3]
确定配对堆每次进行decrease-key操作的均摊时间复杂度是困难的。最初,基于经验,这个操作的时间复杂度被推测为是O(1),[4]但弗雷德曼证明了对于某些操作序列,每次decrease-key操作的时间复杂度至少为。[5] 在那之后,通过不同的均摊依据,Pettie证明了insert、merge及decrease-key操作的均摊时间复杂度均为,近似于。[6] Elmasry后来介绍了一种配对堆的变体,令其拥有所有斐波那契堆可以实现的操作,且decrease-key操作的均摊时间复杂度为,[7]但对于原始的数据结构,仍未知准确的运行下限。[6][3]此外,能否使delete-min在均摊时间复杂度为的同时,令insert操作的均摊时间复杂度为,目前也仍未得到解决。[8]
尽管这比其他的,例如能实现均摊时间的decrease-key的斐波那契堆,这样的优先队列算法更差,在实践中配对堆的表现仍然很不错。Stasko和Vitter,[4] Moret和Shapiro,[9] 以及Larkin、Sen和Tarjan[8] 进行过配对堆和其他堆数据结构的实验。 他们得出的结论是, 配对堆通常比基于数组的二叉堆和D叉堆的实际操作速度更快,而且在实践中几乎总是比其他基于指针的堆更快,其中包括诸如斐波纳契堆这样的理论上更有效率的数据结构。
结构
一个配对堆要么是一个空堆,要么就是一个配对树,由一个根元素与一个可能为空的配对树列表所组成。堆的有序属性使该列表中所有子树的根元素都不小于该堆的根元素。下面描述了一个纯粹的函数堆,我们假定它不支持decrease-key操作。
type PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]]) type PairingHeap[Elem] = Empty | PairingTree[Elem]
对于随机存取机,一个基于指针的实现若要支持decrease-key操作,可以对每个节点使用三个指针做到,具体做法是用单向链表储存节点的孩子:一个指针指向该节点的第一个孩子,一个指向它的下个兄弟,一个指向它的上个兄弟(对于最左边的兄弟则指向它的父亲)。或者,如果使用一个布尔标记表示“链表末尾”且令最后一个孩子指向它的父亲,指向上个兄弟的指针也可以不使用。这在牺牲常数开销的同时,令结构更加紧凑。[1]
操作
find-min(查找最小值)
函数find-min简单地返回该堆的堆顶:
function find-min(heap: PairingHeap[Elem]) -> Elem if heap is Empty error else return heap.elem
merge(合并)
合并一个空堆将会返回另一个堆,否则将会返回一个新堆,其将两个堆的根元素中较小的元素当作新堆的根元素,并将较大的元素所在的堆合并到新堆的子堆中:
function merge(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem] if heap1 is Empty return heap2 elsif heap2 is Empty return heap1 elsif heap1.elem < heap2.elem return Heap(heap1.elem, heap2 :: heap1.subheaps) else return Heap(heap2.elem, heap1 :: heap2.subheaps)
insert(插入)
插入一个元素最简单的方法是,将一个仅有该元素的新堆与需要被插入的堆合并:
function insert(elem: Elem, heap: PairingHeap[Elem]) -> PairingHeap[Elem] return merge(Heap(elem, []), heap)
delete-min(删除最小值)
唯一比较复杂的操作即是堆中最小值的删除操作。标准方法是:首先将子堆从左到右、一对一对地合并(这就是它叫这个名字的原因),然后再从右到左合并该堆。
function delete-min(heap: PairingHeap[Elem]) -> PairingHeap[Elem] if heap is Empty error else return merge-pairs(heap.subheaps)
这需要使用到辅助函数merge-pairs(合并对):
function merge-pairs(list: List[PairingTree[Elem]]) -> PairingHeap[Elem] if length(list) == 0 return Empty elsif length(list) == 1 return list[0] else return merge(merge(list[0], list[1]), merge-pairs(list[2..]))
这确实实现了所描述的两个通过从左向右、然后从右向左的合并策略。这可以下面的过程看到:
merge-pairs([H1, H2, H3, H4, H5, H6, H7]) => merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7])) # 合并H1和H2到H12,再处理列表中剩下的部分 => merge(H12, merge(merge(H3, H4), merge-pairs([H5, H6, H7]))) # 合并H3和H4到H34,再处理列表中剩下的部分 => merge(H12, merge(H34, merge(merge(H5, H6), merge-pairs([H7])))) # 合并H5和H6到H56,再处理列表中剩下的部分 => merge(H12, merge(H34, merge(H56, H7))) # 转换方向,合并最后两个堆,给出H567 => merge(H12, merge(H34, H567)) # 合并最后两个堆,给出H34567 => merge(H12, H34567) # 最终,合并第一个堆和剩下堆合并的结果 => H1234567
运行时间统计
下面的时间复杂度中,[10]O(f)是一个渐近的上界,而Θ(f)是一个准确的上界(见大O符号)。函数名均假设该堆为最小堆。
操作 | 二叉[10] | 左偏 | 二项[10] | 斐波那契[10][11] | 配对[3] | Brodal[12][a] |
---|---|---|---|---|---|---|
find-min | Θ(1) | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) |
delete-min | Θ(log n) | Θ(log n) | Θ(log n) | O(log n)[b] | O(log n)[b] | O(log n) |
insert | O(log n) | Θ(log n) | Θ(1)[b] | Θ(1) | Θ(1) | Θ(1) |
decrease-key | Θ(log n) | Θ(n) | Θ(log n) | Θ(1)[b] | o(log n)[b][c] | Θ(1) |
merge | Θ(n) | Θ(log n) | O(log n)[d] | Θ(1) | Θ(1) | Θ(1) |
参考文献
- ^ 1.0 1.1 1.2 Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. The pairing heap: a new form of self-adjusting heap (PDF). Algorithmica. 1986, 1 (1): 111–129 [2018-04-13]. doi:10.1007/BF01840439. (原始内容存档 (PDF)于2021-05-06).
- ^ Mehlhorn, Kurt; Sanders, Peter. Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. 2008: 231 [2018-04-13]. (原始内容存档 (PDF)于2019-12-31).
- ^ 3.0 3.1 3.2 Iacono, John, Improved upper bounds for pairing heaps, Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science 1851, Springer-Verlag: 63–77, 2000, ISBN 3-540-67690-2, arXiv:1110.4428
, doi:10.1007/3-540-44985-X_5
- ^ 4.0 4.1 Stasko, John T.; Vitter, Jeffrey S., Pairing heaps: experiments and analysis (PDF), Communications of the ACM, 1987, 30 (3): 234–249 [2018-05-20], CiteSeerX 10.1.1.106.2988
, doi:10.1145/214748.214759, (原始内容存档 (PDF)于2017-08-29)
- ^ Fredman, Michael L. On the efficiency of pairing heaps and related data structures (PDF). Journal of the ACM. 1999, 46 (4): 473–501. doi:10.1145/320211.320214. (原始内容 (PDF)存档于2011年7月21日).
- ^ 6.0 6.1 Pettie, Seth, Towards a final analysis of pairing heaps (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183, 2005 [2018-05-20], ISBN 0-7695-2468-0, doi:10.1109/SFCS.2005.75, (原始内容存档 (PDF)于2012-01-28)
- ^ Elmasry, Amr, Pairing heaps with decrease cost (PDF), Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms: 471–476, 2009 [2018-05-20], CiteSeerX 10.1.1.502.6706
, doi:10.1137/1.9781611973068.52, (原始内容存档 (PDF)于2012-10-18)
- ^ 8.0 8.1 Larkin, Daniel H.; Sen, Siddhartha; Tarjan, Robert E., A back-to-basics empirical study of priority queues, Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (PDF): 61–72, 2014, CiteSeerX 10.1.1.638.5198
, arXiv:1403.0252
, doi:10.1137/1.9781611973198.7[永久失效链接]
- ^ Moret, Bernard M. E.; Shapiro, Henry D., An empirical analysis of algorithms for constructing a minimum spanning tree, Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 519, Springer-Verlag: 400–411, 1991 [2018-05-20], CiteSeerX 10.1.1.53.5960
, ISBN 3-540-54343-0, doi:10.1007/BFb0028279, (原始内容存档于2018-07-21)
- ^ 10.0 10.1 10.2 10.3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. Introduction to Algorithms 1st. MIT Press and McGraw-Hill. 1990. ISBN 0-262-03141-8.
- ^ Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms (PDF). Journal of the Association for Computing Machinery. July 1987, 34 (3): 596–615. doi:10.1145/28869.28874.
- ^ Brodal, Gerth S., Worst-Case Efficient Priority Queues (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms: 52–58, 1996
- ^ Goodrich, Michael T.; Tamassia, Roberto. 7.3.6. Bottom-Up Heap Construction. Data Structures and Algorithms in Java 3rd. 2004: 338–341. ISBN 0-471-46983-1.
- ^ Fredman, Michael Lawrence. On the Efficiency of Pairing Heaps and Related Data Structures (PDF). Journal of the Association for Computing Machinery. July 1999, 46 (4): 473–501. doi:10.1145/320211.320214.
- ^ Pettie, Seth. Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183. 2005. CiteSeerX 10.1.1.549.471
. ISBN 0-7695-2468-0. doi:10.1109/SFCS.2005.75.
外部链接
- Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 (页面存档备份,存于互联网档案馆) (pp. 37–52).
- pairing heaps (页面存档备份,存于互联网档案馆), Sartaj Sahni
|
|