问题标题: 配对堆

配对堆(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中的右兄弟结点）。
 

实现：

[java] view plain copy

1. /** 
2.  *  
3.  * Pairing Heap    
4.  *   
5.  * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/) 
6.  * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php)  
7.  *  
8.  * @author ljs 
9.  * 2011-09-06 
10.  * 
11.  */  
12. public class PairingHeap {  
13.     //left-child, right-sibling representation  
14.     static class Node{  
15.         private int key;   
16.           
17.         //left is the parent for first child; is the left sibling for other children  
18.         private Node left;        
19.           
20.         private Node sibling;     
21.           
22.         //child points to the leftmost-child   
23.         private Node child;  
24.                    
25.         public Node(int key){  
26.             this.key = key;  
27.         }  
28.         public String toString(){  
29.             return String.valueOf(this.key);  
30.         }  
31.     }  
32.       
33.     private Node root;  
34.       
35.     private Node linkPair(Node first,Node second){  
36.         if(second==null) return first;  
37.         if(first==null) return second;  
38.           
39.         if(first.key<second.key){  
40.             //second is linked to first as a child  
41.               
42.             //retain the sibling relation  
43.             Node secondzSibling = second.sibling;  
44.             first.sibling = secondzSibling;  
45.             if(secondzSibling != null) secondzSibling.left = first;  
46.               
47.             Node firstzChild = first.child;  
48.               
49.             //update second's left and sibling pointers  
50.             second.left = first;  
51.             second.sibling = firstzChild;  
52.               
53.             //update first.child's pointer  
54.             if(firstzChild != null) firstzChild.left = second;  
55.               
56.             //update first's child  
57.             first.child = second;  
58.             return first;  
59.         }else{  
60.             //first is linked to second as a child  
61.               
62.             //retain the sibling relation  
63.             Node firstzLeft = first.left;  
64.             second.left = firstzLeft;  
65.             if(firstzLeft != null){  
66.                 if(firstzLeft.child == first){  
67.                     //firstzLeft is first's parent  
68.                     firstzLeft.child = second;  
69.                 }else{  
70.                     //firstzLeft is first's left sibling                      
71.                     firstzLeft.sibling = second;  
72.                 }  
73.             }             
74.               
75.             Node secondzChild = second.child;  
76.             //update first's left and sibling pointers  
77.             first.left = second;  
78.             first.sibling = secondzChild;  
79.               
80.             //update second's child pointer  
81.             if(secondzChild != null) secondzChild.left = first;  
82.               
83.             //update second's child  
84.             second.child = first;  
85.             return second;  
86.         }  
87.     }  
88.     public Node insert(Node node){  
89.         if(root==null)   
90.             root = node;  
91.         else  
92.             root = linkPair(node,root);  
93.         return node;  
94.     }  
95.       
96.     public void decreaseKey(Node x,int k) throws Exception{  
97.         if(x.key<k) throw new Exception("key is not decreased!");  
98.         x.key = k;  
99.         if(x!=root){  
100.             //cut x subtree from its siblings  
101.             Node xzLeft = x.left;   
102.             //if x is not root, its left (i.e. xzLeft) can never be null  
103.             if(xzLeft.child==x){//xzLeft is x's parent  
104.                 xzLeft.child = x.sibling;                 
105.             }else{//xzLeft is x's left sibling  
106.                 xzLeft.sibling = x.sibling;  
107.             }  
108.             if(x.sibling!=null){  
109.                 x.sibling.left = xzLeft;  
110.             }  
111.               
112.             //merge this tree with x subtree  
113.             x.left = null;  
114.             x.sibling = null;  
115.             root = this.linkPair(x, root);  
116.         }  
117.     }  
118.       
119.     public void merge(Node rhs){  
120.         if(this.root==null) {  
121.             this.root = rhs;  
122.             return;  
123.         }  
124.         if(rhs==null) return;  
125.           
126.         this.root = this.linkPair(this.root, rhs);  
127.     }  
128.     public Node findMin(){  
129.         return this.root;  
130.     }  
131.       
132.     public Node extractMin(){  
133.         Node z = this.root;  
134.         if(z!=null){  
135.             if(z.child==null)  
136.                 root = null;  
137.             else{  
138.                 Node firstSibling = z.child;  
139.                 firstSibling.left = null;                 
140.                 root = mergeSubHeaps(firstSibling);  
141.             }  
142.         }  
143.         return z;  
144.     }  
145.       
146.     private Node mergeSubHeaps(Node firstSibling){  
147.         //the 1st pass: merge pairs from left side  
148.         Node first = firstSibling;  
149.         Node second = first.sibling;  
150.                   
151.         Node tail = first;  
152.         if(second!=null){  
153.             tail = this.linkPair(first, second);  
154.             first = tail.sibling;  
155.             if(first!= null)  
156.                 second = first.sibling;  
157.             else  
158.                 second = null;  
159.         }  
160.         while(first != null && second!=null){             
161.             tail = this.linkPair(first, second);  
162.             first = tail.sibling;  
163.             if(first!= null)  
164.                 second = first.sibling;       
165.             else  
166.                 second = null;  
167.         }  
168.           
169.         //the 2nd pass: merge pairs from right side  
170.         if(first!=null){  
171.             tail = first;  
172.         }  
173.           
174.         Node prev = tail.left;  
175.         while(prev!=null){  
176.             tail = this.linkPair(prev, tail);  
177.             prev = tail.left;  
178.         }  
179.         return tail;  
180.     }  
181.     public void print(){  
182.         System.out.println("Pairing Heap:");  
183.         this.print(0, this.root);  
184.     }  
185.       
186.     private void print(int level, Node node){  
187.         for (int i = 0; i < level; i++) {  
188.             System.out.format(" ");  
189.         }  
190.         System.out.format("|");  
191.         for (int i = 0; i < level; i++) {  
192.             System.out.format("-");  
193.         }  
194.         System.out.format("%d%n", node.key);  
195.         Node child = node.child;  
196.         while(child!=null){           
197.             print(level + 1, child);  
198.             child = child.sibling;  
199.         }             
200.     }  
201.     public static void main(String[] args) throws Exception {  
202.         PairingHeap pheap = new PairingHeap();  
203.         Node node7=pheap.insert(new Node(7));  
204.         pheap.insert(new Node(19));  
205.         Node node2=pheap.insert(new Node(2));  
206.           
207.         PairingHeap pheap2 = new PairingHeap();  
208.         pheap2.insert(new Node(9));  
209.         pheap2.insert(new Node(17));  
210.         pheap2.insert(new Node(12));  
211.         pheap2.insert(new Node(14));          
212.         pheap.merge(pheap2.root);  
213.           
214.         pheap2 = new PairingHeap();  
215.         pheap2.insert(new Node(15));  
216.         pheap2.insert(new Node(18));  
217.         pheap2.insert(new Node(16));  
218.         pheap2.insert(new Node(5));  
219.         Node node11=pheap2.insert(new Node(11));          
220.         pheap.merge(pheap2.root);  
221.           
222.         pheap2 = new PairingHeap();  
223.         pheap2.insert(new Node(4));  
224.         pheap2.insert(new Node(8));       
225.         pheap.merge(pheap2.root);  
226.           
227.         pheap2 = new PairingHeap();  
228.         Node node3=pheap2.insert(new Node(3));  
229.         pheap2.insert(new Node(13));  
230.         pheap2.insert(new Node(10));  
231.         pheap.merge(pheap2.root);  
232.           
233.         pheap.insert(new Node(6));  
234.           
235.         pheap.print();  
236.           
237.         Node min = pheap.findMin();  
238.         System.out.format("min: %d%n", min.key);  
239.           
240.         pheap.decreaseKey(node11, 0);  
241.         pheap.decreaseKey(node7, 4);  
242.         pheap.decreaseKey(node2, 1);  
243.         pheap.decreaseKey(node3, 2);  
244.           
245.         min = pheap.extractMin();  
246.         while(min!=null){  
247.             System.out.format("%d ",min.key);  
248.             min = pheap.extractMin();         
249.         }  
250.     }  
251.   
252. }  

测试输出：

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