斜堆(三)之Java的实现

  1 /**
  2  * Java 语言: 斜堆
  3  *
  4  * @author skywang
  5  * @date 2014/03/31
  6  */
  7 
  8 public class SkewHeapextends Comparable> {
  9 
 10     private SkewNode mRoot;    // 根结点
 11 
 12     private class SkewNodeextends Comparable> {
 13         T key;                // 关键字(键值)
 14         SkewNode left;    // 左孩子
 15         SkewNode right;    // 右孩子
 16 
 17         public SkewNode(T key, SkewNode left, SkewNode right) {
 18             this.key = key;
 19             this.left = left;
 20             this.right = right;
 21         }
 22 
 23         public String toString() {
 24             return "key:"+key;
 25         }
 26     }
 27 
 28     public SkewHeap() {
 29         mRoot = null;
 30     }
 31 
 32     /*
 33      * 前序遍历"斜堆"
 34      */
 35     private void preOrder(SkewNode heap) {
 36         if(heap != null) {
 37             System.out.print(heap.key+" ");
 38             preOrder(heap.left);
 39             preOrder(heap.right);
 40         }
 41     }
 42 
 43     public void preOrder() {
 44         preOrder(mRoot);
 45     }
 46 
 47     /*
 48      * 中序遍历"斜堆"
 49      */
 50     private void inOrder(SkewNode heap) {
 51         if(heap != null) {
 52             inOrder(heap.left);
 53             System.out.print(heap.key+" ");
 54             inOrder(heap.right);
 55         }
 56     }
 57 
 58     public void inOrder() {
 59         inOrder(mRoot);
 60     }
 61 
 62     /*
 63      * 后序遍历"斜堆"
 64      */
 65     private void postOrder(SkewNode heap) {
 66         if(heap != null)
 67         {
 68             postOrder(heap.left);
 69             postOrder(heap.right);
 70             System.out.print(heap.key+" ");
 71         }
 72     }
 73 
 74     public void postOrder() {
 75         postOrder(mRoot);
 76     }
 77 
 78     /*
 79      * 合并"斜堆x"和"斜堆y"
 80      */
 81     private SkewNode merge(SkewNode x, SkewNode y) {
 82         if(x == null) return y;
 83         if(y == null) return x;
 84 
 85         // 合并x和y时，将x作为合并后的树的根；
 86         // 这里的操作是保证: x的key 
 87         if(x.key.compareTo(y.key) > 0) {
 88             SkewNode tmp = x;
 89             x = y;
 90             y = tmp;
 91         }
 92 
 93         // 将x的右孩子和y合并，
 94         // 合并后直接交换x的左右孩子，而不需要像左倾堆一样考虑它们的npl。
 95         SkewNode tmp = merge(x.right, y);
 96         x.right = x.left;
 97         x.left = tmp;
 98 
 99         return x;
100     }
101 
102     public void merge(SkewHeap other) {
103         this.mRoot = merge(this.mRoot, other.mRoot);
104     }
105 
106     /* 
107      * 新建结点(key)，并将其插入到斜堆中
108      *
109      * 参数说明：
110      *     key 插入结点的键值
111      */
112     public void insert(T key) {
113         SkewNode node = new SkewNode(key,null,null);
114 
115         // 如果新建结点失败，则返回。
116         if (node != null)
117             this.mRoot = merge(this.mRoot, node);
118     }
119 
120     /* 
121      * 删除根结点
122      * 
123      * 返回值：
124      *     返回被删除的节点的键值
125      */
126     public T remove() {
127         if (this.mRoot == null)
128             return null;
129 
130         T key = this.mRoot.key;
131         SkewNode l = this.mRoot.left;
132         SkewNode r = this.mRoot.right;
133 
134         this.mRoot = null;          // 删除根节点
135         this.mRoot = merge(l, r);   // 合并左右子树
136 
137         return key;
138     }
139 
140     /*
141      * 销毁斜堆
142      */
143     private void destroy(SkewNode heap) {
144         if (heap==null)
145             return ;
146 
147         if (heap.left != null)
148             destroy(heap.left);
149         if (heap.right != null)
150             destroy(heap.right);
151 
152         heap=null;
153     }
154 
155     public void clear() {
156         destroy(mRoot);
157         mRoot = null;
158     }
159 
160     /*
161      * 打印"斜堆"
162      *
163      * key        -- 节点的键值 
164      * direction  --  0，表示该节点是根节点;
165      *               -1，表示该节点是它的父结点的左孩子;
166      *                1，表示该节点是它的父结点的右孩子。
167      */
168     private void print(SkewNode heap, T key, int direction) {
169 
170         if(heap != null) {
171 
172             if(direction==0)    // heap是根节点
173                 System.out.printf("%2d is root\n", heap.key);
174             else                // heap是分支节点
175                 System.out.printf("%2d is %2d's %6s child\n", heap.key, key, direction==1?"right" : "left");
176 
177             print(heap.left, heap.key, -1);
178             print(heap.right,heap.key,  1);
179         }
180     }
181 
182     public void print() {
183         if (mRoot != null)
184             print(mRoot, mRoot.key, 0);
185     }
186 }

 1 /**
 2  * Java 语言: 斜堆
 3  *
 4  * @author skywang
 5  * @date 2014/03/31
 6  */
 7 
 8 public class SkewHeapTest {
 9 
10     public static void main(String[] args) {
11 
12         int a[]= {10,40,24,30,36,20,12,16};
13         int b[]= {17,13,11,15,19,21,23};
14         SkewHeap ha=new SkewHeap();
15         SkewHeap hb=new SkewHeap();
16 
17         System.out.printf("== 斜堆(ha)中依次添加: ");
18         for(int i=0; i) {
19             System.out.printf("%d ", a[i]);
20             ha.insert(a[i]);
21         }
22         System.out.printf("\n== 斜堆(ha)的详细信息: \n");
23         ha.print();
24 
25 
26         System.out.printf("\n== 斜堆(hb)中依次添加: ");
27         for(int i=0; i) {
28             System.out.printf("%d ", b[i]);
29             hb.insert(b[i]);
30         }
31         System.out.printf("\n== 斜堆(hb)的详细信息: \n");
32         hb.print();
33 
34         // 将"斜堆hb"合并到"斜堆ha"中。
35         ha.merge(hb);
36         System.out.printf("\n== 合并ha和hb后的详细信息: \n");
37         ha.print();
38     }
39 }