问题标题: 斜堆

斜堆(Skew Heap)基于左倾堆的概念，也是一个用于快速合并的堆结构，但它可自我调整(self-adjusting)，每一个merge操作的平摊成本仍为O(logN)，其中N为结点数，而且和左倾堆相比，每个结点没有npl属性，从而节省了空间。斜堆并不能保证左倾，但是每一个合并操作（也是采取右路合并）同时需要无条件交换（而左倾堆中只是根据左右子树的npl值不符合要求时才交换）左右子树，让新合并的右子树变成左子树，原来的左子树变成新的右子树（这有点类似于Splay Tree中的做法），从而可以达到平摊意义上的左倾效果。注意：一颗子树r和NULL子树合并时并不需要交换r子树的左右子树。

由于斜堆并不是严格的左倾堆，最坏的情况下右路长度可能为N，因此采用递归调用merge的风险是出现stack overflow。尽管如此，在下面的实现中还是提供了递归和非递归的两个版本。测试时使用的是非递归版本。

斜堆中除merge之外的其他操作跟左倾堆类似，具体情况参考以下代码，在此不再赘述。
 

实现：

[java] view plain copy

1. import java.util.LinkedList;  
2. import java.util.Stack;  
3.   
4.    
5.   
6. /** 
7.  *  
8.  * Skew Heap    
9.  *   
10.  * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/) 
11.  * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php)  
12.  *  
13.  * @author ljs 
14.  * 2011-08-25 
15.  * 
16.  */  
17. public class SkewHeap {  
18.     static class Node{  
19.         int key;  
20.         Node left;  
21.         Node right;  
22.           
23.         public Node(int key){  
24.             this.key = key;   
25.         }  
26.           
27.         public String toString(){  
28.             return String.valueOf(this.key);  
29.         }  
30.           
31.         public Node recursiveMerge(Node rhsRoot){  
32.             if(rhsRoot==this || rhsRoot == null) {  
33.                 //Note: no need to swap the left and right children of this tree  
34.                 //Node tmp = this.left;  
35.                 //this.left = this.right;  
36.                 //this.right = tmp;  
37.                 return this;  
38.             }  
39.               
40.             Node root1 = null; //the root of the merged tree  
41.             Node root2 = null;   
42.             if(rhsRoot.key<this.key){  
43.                 //merge this with rhsRoot's right child  
44.                 root1 = rhsRoot;  
45.                 root2 = this;  
46.             }else{  
47.                 //merge rhsRoot with this's right child  
48.                 root1 = this;  
49.                 root2 = rhsRoot;                  
50.             }  
51.               
52.             Node tmpRoot = root2.recursiveMerge(root1.right);  
53.             root1.right = root1.left;  
54.             root1.left = tmpRoot;  
55.             //or equivalently: we may first merge recursively, then swap left and right children.  
56.             //Node right = root1.right;  
57.             //root1.right = root1.left;            
58.             //root1.left = root2.merge(right);            
59.                           
60.             return root1;  
61.         }  
62.     }  
63.     private Node root;  
64.       
65.     public SkewHeap(Node root){  
66.         this.root = root;  
67.     }  
68.       
69.     //version 1: recursive merge: not recommended because skew heap is   
70.     //unlike leftist heap to be deterministically leftist, so it can cause   
71.     //stack overflow in extreme cases.  
72.     private static Node recursiveMerge(Node root1,Node root2){  
73.         if(root1 == null) return root2;  
74.         if(root2 == null) return root1;  
75.         return root1.recursiveMerge(root2);   
76.     }     
77.   
78.     //version 2: non-recursive merge  
79.     private static Node iterativeMerge(Node root1,Node root2){  
80.         if(root1 == null) return root2;  
81.         if(root2 == null) return root1;  
82.           
83.         Stack<Node> stack = new Stack<Node>();  
84.         Node r1 = root1;  
85.         Node r2 = root2;  
86.         while(r1 != null && r2 != null){  
87.             if(r1.key<r2.key){  
88.                 stack.push(r1);  
89.                 r1 = r1.right;  
90.             }else{  
91.                 stack.push(r2);  
92.                 r2 = r2.right;  
93.             }             
94.         }  
95.         //at this point, exactly one of r1 and r2 is null  
96.         //Again we don't need to swap the left and right children of r  
97.         Node r = (r1 != null)?r1:r2;  
98.           
99.         //merge  
100.         while(!stack.isEmpty()){  
101.             Node node = stack.pop();              
102.             node.right = node.left;  
103.             node.left = r;  
104.             r = node;  
105.         }  
106.         return r;  
107.     }  
108.       
109.     public static SkewHeap merge(SkewHeap h1,SkewHeap h2){  
110.         Node rootNode = iterativeMerge(h1.root,h2.root);  
111.         return new SkewHeap(rootNode);  
112.     }        
113.       
114.     public static SkewHeap buildHeap(int[] A){  
115.         LinkedList<Node> queue = new LinkedList<Node>();  
116.         int n = A.length;  
117.         //init: queue all elements as a single-node tree  
118.         for(int i=0;i<n;i++){  
119.             Node node = new Node(A[i]);  
120.             queue.add(node);  
121.         }  
122.         //merge adjacent heaps and enqueue the merged heap afterward  
123.         while(queue.size()>1){  
124.             Node root1 = queue.remove(); //dequeue  
125.             Node root2 = queue.remove();  
126.             Node rootNode = iterativeMerge(root1,root2);  
127.             queue.add(rootNode);  
128.         }  
129.         Node rootNode = queue.remove();  
130.         return new SkewHeap(rootNode);  
131.     }  
132.     public void insert(int x){  
133.         this.root = SkewHeap.iterativeMerge(new Node(x), this.root);  
134.     }  
135.       
136.     public Integer extractMin(){  
137.         if(this.root == null) return null;  
138.           
139.         int min = this.root.key;  
140.         this.root = SkewHeap.iterativeMerge(this.root.left, this.root.right);  
141.         return min;  
142.     }  
143.        
144.       
145.     public static void main(String[] args) {  
146.         int[] A = new int[]{4,8,10,9,1,3,5,6,11};  
147.            
148.          SkewHeap heap = SkewHeap.buildHeap(A);  
149.          heap.insert(7);  
150.          Integer min = null;  
151.          while((min = heap.extractMin()) != null){  
152.              System.out.format(" %d", min);  
153.          }  
154.          System.out.println();  
155.            
156.          System.out.println("********************");  
157.          A = new int[]{3,10,8,21,14,17,23,26};  
158.            
159.            
160.          Node a0 = new Node(A[0]);  
161.          Node a1 = new Node(A[1]);  
162.          Node a2 = new Node(A[2]);  
163.          Node a3 = new Node(A[3]);  
164.          Node a4 = new Node(A[4]);  
165.          Node a5 = new Node(A[5]);  
166.          Node a6 = new Node(A[6]);  
167.          Node a7 = new Node(A[7]);         
168.          a0.left = a1;     
169.          a0.right = a2;   
170.          a1.left = a3;     
171.          a1.right = a4;  
172.          a4.left = a6;  
173.          a2.left = a5;  
174.          a5.left = a7;  
175.          SkewHeap h1 = new SkewHeap(a0);  
176.            
177.          int[] B = new int[]{6,12,7,18,24,37,18,33};  
178.          Node b0 = new Node(B[0]);  
179.          Node b1 = new Node(B[1]);  
180.          Node b2 = new Node(B[2]);  
181.          Node b3 = new Node(B[3]);  
182.          Node b4 = new Node(B[4]);  
183.          Node b5 = new Node(B[5]);  
184.          Node b6 = new Node(B[6]);  
185.          Node b7 = new Node(B[7]);  
186.          b0.left = b1;    
187.          b0.right = b2;  
188.          b1.left = b3;    
189.          b1.right = b4;   
190.          b4.left = b7;  
191.          b2.left = b5;    
192.          b2.right = b6;  
193.          SkewHeap h2 = new SkewHeap(b0);  
194.            
195.          heap = SkewHeap.merge(h1,h2);  
196.          while((min = heap.extractMin()) != null){  
197.              System.out.format(" %d", min);  
198.          }  
199.          System.out.println();   
200.            
201.          System.out.println("********************");  
202.          A = new int[]{1,4,23,63,24,44,28};  
203.          a0 = new Node(A[0]);  
204.          a1 = new Node(A[1]);  
205.          a2 = new Node(A[2]);  
206.          a3 = new Node(A[3]);  
207.          a4 = new Node(A[4]);  
208.          a5 = new Node(A[5]);  
209.          a6 = new Node(A[6]);   
210.          a0.left = a1;     
211.          a0.right = a2;  
212.          a1.left = a3;     
213.          a1.right = a4;  
214.          a2.left = a5;    
215.          a2.right = a6;  
216.          h1 = new SkewHeap(a0);  
217.            
218.          B = new int[]{13,17,99,57,49,105,201};  
219.          b0 = new Node(B[0]);  
220.          b1 = new Node(B[1]);  
221.          b2 = new Node(B[2]);  
222.          b3 = new Node(B[3]);  
223.          b4 = new Node(B[4]);  
224.          b5 = new Node(B[5]);  
225.          b6 = new Node(B[6]);  
226.          b0.left = b1;  
227.          b0.right = b2;  
228.          b1.left = b3;  
229.          b1.right = b4;  
230.          b2.left = b5;  
231.          b2.right = b6;  
232.          h2 = new SkewHeap(b0);  
233.            
234.          heap = SkewHeap.merge(h1,h2);   
235.          while((min = heap.extractMin()) != null){  
236.              System.out.format(" %d", min);  
237.          }  
238.          System.out.println();  
239.     }  
240.   
241. }  

测试输出：
 1 3 4 5 6 7 8 9 10 11
********************
 3 6 7 8 10 12 14 17 18 18 21 23 24 26 33 37
********************
 1 4 13 17 23 24 28 44 49 57 63 99 105 201