斐波那契堆

  1 public class FibHeap 
  2 {
  3     private FibNode min;
  4     
  5     private int count;
  6     
  7     private FibNode root;
  8 
  9     
 10     public FibHeap() 
 11     {
 12         root = new FibNode();
 13         root.left  = root;
 14         root.right = root;
 15     }
 16 
 17     /*
 18      * 返回最小节点
 19      */
 20     public FibNode min() 
 21     {
 22         return min;
 23     }
 24 
 25     /*
 26      * 删除节点
 27      */
 28     public void delete(FibNode node) 
 29     {
 30         decereaseKey(node, Integer.MIN_VALUE);
 31         extractMin();
 32     }
 33     
 34     /*
 35      * 减小某结点的值
 36      */
 37     public void decereaseKey(FibNode node, int k) 
 38     {
 39         if (node.key < k) {
 40             throw new RuntimeException("new key is greater than current key");
 41         }
 42         
 43         node.key = k;
 44         FibNode parent = node.parent;
 45         if (parent != null && node.key < parent.key) {
 46             cut(node, parent);
 47             cascadingCut(parent);
 48         }
 49         
 50         if (node.key < min.key) min = node;
 51     }
 52 
 53     /*
 54      * 剔除node节点并执行insertRoot
 55      */
 56     public void cut(FibNode node, FibNode parent) 
 57     {
 58         node.left.right = node.right;
 59         node.right.left = node.left;
 60         parent.degree--;
 61         
 62         insertRoot(node);
 63         node.parent = null;
 64         node.mark = false;
 65     }
 66 
 67     /*
 68      * ?????? 
 69      */
 70     public void cascadingCut(FibNode node) 
 71     {
 72         FibNode parent = node.parent;
 73         if (parent != null) {
 74             if (!node.mark) {
 75                 node.mark = true;
 76             }
 77             else {
 78                 cut(node, parent);
 79                 cascadingCut(parent);
 80             }
 81         }
 82     }
 83 
 84     /*
 85      * 抽取最小关键子节点
 86      */
 87     public FibNode extractMin() 
 88     {
 89         FibNode node = min;
 90         if (node != null) {
 91             
 92             if (node.degree != 0) {
 93                 FibNode child = node.child;
 94                 FibNode next = child;
 95                 
 96                 do {
 97                     next.parent = null;
 98                     next = next.right;
 99                 }
100                 while (child != next);
101                 
102                 node.left.right = child.right;
103                 child.right.left = node.left;
104                 node.right.left = child;
105                 child.right = node.right;
106             }
107             else {
108                 node.left.right = node.right;
109                 node.right.left = node.left;
110             }
111             
112             if (node == node.right) {
113                 min = null;
114             }
115             else {
116                 min = min.right;
117                 consolidate();
118             }
119             count--;
120         }
121         return node;
122     }
123 
124     /*
125      * 输出根节点
126      */
127     public void displayRoot() 
128     {
129         FibNode node = root.right;
130         while (node != root) {
131             System.out.println(node.key);
132             node = node.right;
133         }
134     }
135 
136     /*
137      * 合并
138      */
139     public void consolidate() 
140     {
141         FibNode[] array = new FibNode[(int) (Math.log(count) / Math.log(2)) + 1];
142         
143         FibNode node = root.right;
144         while (node != root) {
145             FibNode nodex = node;
146             node = node.right;
147             int degree = nodex.degree;
148             
149             while (array[degree] != null) {
150                 FibNode nodey = array[degree];
151                 if (nodex.key > nodey.key) {
152                     // swap
153                     FibNode temp = nodex;
154                     nodex = nodey;
155                     nodey = temp;
156                 }
157                 link(nodey, nodex);
158                 array[degree++] = null;
159             }
160             array[degree] = nodex;
161         }
162         
163         min = null;
164         for (int i = 0; i < array.length; i++) {
165             if (array[i] != null) {
166                 if (min == null || array[i].key < min.key) {
167                     min = array[i];
168                 }
169             }
170         }
171     }
172 
173     /*
174      * 连接节点
175      */
176     public void link(FibNode node, FibNode parent) 
177     {
178         node.left.right = node.right;
179         node.right.left = node.left;
180         node.parent = parent;
181         
182         if (parent.degree == 0) {
183             parent.child = node;
184             node.left = node;
185             node.right = node;
186         }
187         else {
188             node.left = parent.child.left;
189             parent.child.left.right = node;
190             node.right = parent.child;
191             parent.child.left = node;
192         }
193         
194         parent.degree++;
195         node.mark = false;
196     }
197 
198     /*
199      * 插入节点
200      */
201     public void insert(FibNode node) 
202     {
203         node.degree = 0;
204         node.parent = null;
205         node.child = null;
206         node.left = node;
207         node.right = node;
208         node.mark = false;
209         
210         insertRoot(node);
211         
212         if (min == null || node.key < min.key) {
213             min = node;
214         }
215         count++;
216     }
217 
218     /*
219      * 合并两个堆
220      */
221     public void union(FibHeap heap) 
222     {
223         if (heap.count == 0) return;
224 
225         FibNode node = heap.root;
226         node.right.left = root.left;
227         root.left.right = node.right;
228         node.left.right = root;
229         root.left.left = node;
230         
231         if (min == null || heap.min.key < min.key) {
232             min = heap.min;
233         }
234         count += heap.count;
235     }
236 
237     /*
238      * 插入Root节点
239      */
240     private void insertRoot(FibNode node) 
241     {
242         /*
243          *  left  node  root
244          *    O-----O-----O
245          */
246         
247         node.left = root.left;
248         root.left.right = node;
249         node.right = root;
250         root.left = node;
251     }
252 
253     static class FibNode 
254     {
255         FibNode child;
256         
257         FibNode left;
258         
259         FibNode right;
260         
261         FibNode parent;
262         
263         int degree = 0;
264         
265         boolean mark = false;
266         
267         int key;
268         
269         
270         public FibNode() {}
271         
272         public FibNode(int key)
273         {
274             this.key = key;
275         }
276     }
277 
278     public static void main(String[] args) 
279     {
280         FibHeap fh = new FibHeap();
281         
282         int[] keys = { 9, 10, 5, 14, 12, 13, 8, 3 };
283         for (int i = 0; i < keys.length; i++) {
284             fh.insert(new FibNode(keys[i]));
285         }
286         
287         FibHeap fh2 = new FibHeap();
288         
289         int[] keys2 = { 3,7,2,7,9,14,66};
290         for (int i = 0; i < keys2.length; i++) {
291             FibNode fn=new FibNode();
292             fh2.insert(new FibNode(keys2[i]));
293         }
294         
295         fh.union(fh2);
296         System.out.println(fh.min().key);
297         
298         fh.displayRoot();
299         System.out.println("min:" + fh.extractMin().key);
300         System.out.println("min:" + fh.extractMin().key);
301         System.out.println("min:" + fh.extractMin().key);
302 
303         fh.delete(fh.min());
304         System.out.println(fh.min().key);
305     }
306 }