配对堆(Pairing Heap)是一个简单实用的min-heap结构（当然也可以做成max-heap）。它是一颗多路树(multiway tree)，类似于Leftist Heap和Skew Heap，但是与Binomial Tree和Fibonacci Heap不一样。它的基本操作是两个多路树的连接(link)，所以取名叫Pairing Heap。连接操作(参考以下实现中的方法linkPair)类似于Binomial Tree和Fibonacci Heap中的link操作，即将root key值最大的树作为key值最小的树的孩子（一般作为最左边的孩子，特别是Binomial Heap必须这样做），其复杂度是常数级。因为Pairing Heap只有一棵树，所以它的merge操作(类似于Fibonacci Heap中的union)也很简单，只需要link两棵树就可以了，平摊复杂度与Fibonacci Heap类似，都是常数级操作，而在Binomial Heap中需要union两个root lists，所以复杂度为O(logn)。在算法分析中，往往有很多数据结构实现起来比较简单，但是分析起来很复杂，例如快速排序 (Quicksort)，配对堆也是一个典型例子。配对堆的merge，insert和findMin的平摊复杂度都是O(1)，extract-min 的平摊复杂度是O(logn)，这与Fibonacci Heap中的相应操作的复杂度相当。但是，decrease-key的平摊复杂度比Fibonacci Heap大，后者的decrease-key的平摊复杂度是O(1)。关于配对堆的decrease-key操作的平摊复杂度结果可以参 考：http://en.wikipedia.org/wiki/Pairing_heap。 在以下实现中，Pairing Heap采用“leftmost child,right sibling”（左孩子，右兄弟）方式表示，而且每一个结点还有一个left属性：对于第一个孩子，left属性表示该孩子的父结点；对于其他结 点，left属性表示该结点的左兄弟。Extract-Min操作比较有意思，首先采用类似Binomial Heap和Fibonacci Heap中做法，即先删除root结点，然后得到root的孩子结点双向链表，链表中每一个结点对应一个子堆(subheap)；接下来考虑如何将子堆合 并到原来的堆中，在这里可以比较一下二项堆，Fibonacci堆和配对堆的合并做法：在Binomial Heap中将孩子结点倒排，生成按degree从小到大顺序的单向链表，然后将该单链表跟原来剩余的堆结点root list链表作union操作。在Fibonacci Heap中的做法是，将孩子结点依次添加到root list中（不用考虑先后次序），然后通过consolidate生成degree唯一的双向循环链表。二者都是在Extract-min时让每个堆结构 变得更加紧凑，恢复成理想的状态，同时Extract-min的操作成本也相对比较高。在Pairing Heap中做法类似：如果没有Extract-min操作，其他的操作（比如insert,merge，decrease-key）势必使得root结点 的孩子链表变得很长，通过Extract-Min两两合并，让Pairing Heap变得更加有序。Extract-Min两两合并做法是：先从左到右将相邻的孩子结点两两link，生成一个缩减的双向链表，然后对该新的双向链表从右到左link（上一次合并的结果作为下一次link中的右兄弟结点）。
实现：
/** * * Pairing Heap * * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/) * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php) * * @author ljs * 2011-09-06 * */ public class PairingHeap { //left-child, right-sibling representation static class Node{ private int key; //left is the parent for first child; is the left sibling for other children private Node left; private Node sibling; //child points to the leftmost-child private Node child; public Node(int key){ this.key = key; } public String toString(){ return String.valueOf(this.key); } } private Node root; private Node linkPair(Node first,Node second){ if(second==null) return first; if(first==null) return second; if(first.key
测试输出：
Pairing Heap:
|2 |-6 |-3 |--10 |--13 |-4 |--8 |-5 |--11 |--15 |---16 |---18 |-9 |--14 |--12 |--17 |-7 |--19
min: 2
0 1 2 4 4 5 6 8 9 10 12 13 14 15 16 17 18 19
延伸阅读
最新评论