KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > util > FibonacciHeap


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (barak_naveh@users.sourceforge.net)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* --------------------------
26  * FibonnaciHeap.java
27  * --------------------------
28  * (C) Copyright 1999-2003, by Nathan Fiedler and Contributors.
29  *
30  * Original Author: Nathan Fiedler
31  * Contributor(s): John V. Sichi
32  *
33  * $Id: FibonacciHeap.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 03-Sept-2003 : Adapted from Nathan Fiedler (JVS);
38  *
39  * Name Date Description
40  * ---- ---- -----------
41  * nf 08/31/97 Initial version
42  * nf 09/07/97 Removed FibHeapData interface
43  * nf 01/20/01 Added synchronization
44  * nf 01/21/01 Made Node an inner class
45  * nf 01/05/02 Added clear(), renamed empty() to
46  * isEmpty(), and renamed printHeap()
47  * to toString()
48  * nf 01/06/02 Removed all synchronization
49  *
50  */
51 package org.jgrapht.util;
52
53 import java.util.*;
54
55
56 /**
57  * This class implements a Fibonacci heap data structure. Much of the code in
58  * this class is based on the algorithms in the "Introduction to Algorithms"by
59  * Cormen, Leiserson, and Rivest in Chapter 21. The amortized running time of
60  * most of these methods is O(1), making it a very fast data structure. Several
61  * have an actual running time of O(1). removeMin() and delete() have O(log n)
62  * amortized running times because they do the heap consolidation. If you
63  * attempt to store nodes in this heap with key values of -Infinity
64  * (Double.NEGATIVE_INFINITY) the <code>delete()</code> operation may fail to
65  * remove the correct element.
66  *
67  * <p><b>Note that this implementation is not synchronized.</b> If multiple
68  * threads access a set concurrently, and at least one of the threads modifies
69  * the set, it <i>must</i> be synchronized externally. This is typically
70  * accomplished by synchronizing on some object that naturally encapsulates the
71  * set.</p>
72  *
73  * <p>This class was originally developed by Nathan Fiedler for the GraphMaker
74  * project. It was imported to JGraphT with permission, courtesy of Nathan
75  * Fiedler.</p>
76  *
77  * @author Nathan Fiedler
78  */
79 public class FibonacciHeap<T>
80 {
81
82     //~ Instance fields -------------------------------------------------------
83
84     /**
85      * Points to the minimum node in the heap.
86      */
87     private FibonacciHeapNode<T> minNode;
88
89     /**
90      * Number of nodes in the heap.
91      */
92     private int nNodes;
93
94     //~ Constructors ----------------------------------------------------------
95
96     /**
97      * Constructs a FibonacciHeap object that contains no elements.
98      */
99     public FibonacciHeap()
100     {
101     } // FibonacciHeap
102
103     //~ Methods ---------------------------------------------------------------
104
105     /**
106      * Tests if the Fibonacci heap is empty or not. Returns true if the heap is
107      * empty, false otherwise.
108      *
109      * <p>Running time: O(1) actual</p>
110      *
111      * @return true if the heap is empty, false otherwise
112      */
113     public boolean isEmpty()
114     {
115         return minNode == null;
116     }
117
118     // isEmpty
119
120     /**
121      * Removes all elements from this heap.
122      */
123     public void clear()
124     {
125         minNode = null;
126         nNodes = 0;
127     }
128
129     // clear
130
131     /**
132      * Decreases the key value for a heap node, given the new value to take on.
133      * The structure of the heap may be changed and will not be consolidated.
134      *
135      * <p>Running time: O(1) amortized</p>
136      *
137      * @param x node to decrease the key of
138      * @param k new key value for node x
139      *
140      * @exception IllegalArgumentException Thrown if k is larger than x.key
141      * value.
142      */
143     public void decreaseKey(FibonacciHeapNode<T> x, double k)
144     {
145         if (k > x.key) {
146             throw new IllegalArgumentException JavaDoc(
147                 "decreaseKey() got larger key value");
148         }
149
150         x.key = k;
151
152         FibonacciHeapNode<T> y = x.parent;
153
154         if ((y != null) && (x.key < y.key)) {
155             cut(x, y);
156             cascadingCut(y);
157         }
158
159         if (x.key < minNode.key) {
160             minNode = x;
161         }
162     }
163
164     // decreaseKey
165
166     /**
167      * Deletes a node from the heap given the reference to the node. The trees
168      * in the heap will be consolidated, if necessary. This operation may fail
169      * to remove the correct element if there are nodes with key value
170      * -Infinity.
171      *
172      * <p>Running time: O(log n) amortized</p>
173      *
174      * @param x node to remove from heap
175      */
176     public void delete(FibonacciHeapNode<T> x)
177     {
178         // make x as small as possible
179 decreaseKey(x, Double.NEGATIVE_INFINITY);
180
181         // remove the smallest, which decreases n also
182 removeMin();
183     }
184
185     // delete
186
187     /**
188      * Inserts a new data element into the heap. No heap consolidation is
189      * performed at this time, the new node is simply inserted into the root
190      * list of this heap.
191      *
192      * <p>Running time: O(1) actual</p>
193      *
194      * @param node new node to insert into heap
195      * @param key key value associated with data object
196      */
197     public void insert(FibonacciHeapNode<T> node, double key)
198     {
199         node.key = key;
200
201         // concatenate node into min list
202 if (minNode != null) {
203             node.left = minNode;
204             node.right = minNode.right;
205             minNode.right = node;
206             node.right.left = node;
207
208             if (key < minNode.key) {
209                 minNode = node;
210             }
211         } else {
212             minNode = node;
213         }
214
215         nNodes++;
216     }
217
218     // insert
219
220     /**
221      * Returns the smallest element in the heap. This smallest element is the
222      * one with the minimum key value.
223      *
224      * <p>Running time: O(1) actual</p>
225      *
226      * @return heap node with the smallest key
227      */
228     public FibonacciHeapNode<T> min()
229     {
230         return minNode;
231     }
232
233     // min
234
235     /**
236      * Removes the smallest element from the heap. This will cause the trees in
237      * the heap to be consolidated, if necessary.
238      *
239      * <p>Running time: O(log n) amortized</p>
240      *
241      * @return node with the smallest key
242      */
243     public FibonacciHeapNode<T> removeMin()
244     {
245         FibonacciHeapNode<T> z = minNode;
246
247         if (z != null) {
248             int numKids = z.degree;
249             FibonacciHeapNode<T> x = z.child;
250             FibonacciHeapNode<T> tempRight;
251
252             // for each child of z do...
253 while (numKids > 0) {
254                 tempRight = x.right;
255
256                 // remove x from child list
257 x.left.right = x.right;
258                 x.right.left = x.left;
259
260                 // add x to root list of heap
261 x.left = minNode;
262                 x.right = minNode.right;
263                 minNode.right = x;
264                 x.right.left = x;
265
266                 // set parent[x] to null
267 x.parent = null;
268                 x = tempRight;
269                 numKids--;
270             }
271
272             // remove z from root list of heap
273 z.left.right = z.right;
274             z.right.left = z.left;
275
276             if (z == z.right) {
277                 minNode = null;
278             } else {
279                 minNode = z.right;
280                 consolidate();
281             }
282
283             // decrement size of heap
284 nNodes--;
285         }
286
287         return z;
288     }
289
290     // removeMin
291
292     /**
293      * Returns the size of the heap which is measured in the number of elements
294      * contained in the heap.
295      *
296      * <p>Running time: O(1) actual</p>
297      *
298      * @return number of elements in the heap
299      */
300     public int size()
301     {
302         return nNodes;
303     }
304
305     // size
306
307     /**
308      * Joins two Fibonacci heaps into a new one. No heap consolidation is
309      * performed at this time. The two root lists are simply joined together.
310      *
311      * <p>Running time: O(1) actual</p>
312      *
313      * @param h1 first heap
314      * @param h2 second heap
315      *
316      * @return new heap containing h1 and h2
317      */
318     public static <T> FibonacciHeap<T> union(
319         FibonacciHeap<T> h1,
320         FibonacciHeap<T> h2)
321     {
322         FibonacciHeap<T> h = new FibonacciHeap<T>();
323
324         if ((h1 != null) && (h2 != null)) {
325             h.minNode = h1.minNode;
326
327             if (h.minNode != null) {
328                 if (h2.minNode != null) {
329                     h.minNode.right.left = h2.minNode.left;
330                     h2.minNode.left.right = h.minNode.right;
331                     h.minNode.right = h2.minNode;
332                     h2.minNode.left = h.minNode;
333
334                     if (h2.minNode.key < h1.minNode.key) {
335                         h.minNode = h2.minNode;
336                     }
337                 }
338             } else {
339                 h.minNode = h2.minNode;
340             }
341
342             h.nNodes = h1.nNodes + h2.nNodes;
343         }
344
345         return h;
346     }
347
348     // union
349
350     /**
351      * Creates a String representation of this Fibonacci heap.
352      *
353      * @return String of this.
354      */
355     public String JavaDoc toString()
356     {
357         if (minNode == null) {
358             return "FibonacciHeap=[]";
359         }
360
361         // create a new stack and put root on it
362 Stack<FibonacciHeapNode<T>> stack = new Stack<FibonacciHeapNode<T>>();
363         stack.push(minNode);
364
365         StringBuffer JavaDoc buf = new StringBuffer JavaDoc(512);
366         buf.append("FibonacciHeap=[");
367
368         // do a simple breadth-first traversal on the tree
369 while (!stack.empty()) {
370             FibonacciHeapNode<T> curr = stack.pop();
371             buf.append(curr);
372             buf.append(", ");
373
374             if (curr.child != null) {
375                 stack.push(curr.child);
376             }
377
378             FibonacciHeapNode<T> start = curr;
379             curr = curr.right;
380
381             while (curr != start) {
382                 buf.append(curr);
383                 buf.append(", ");
384
385                 if (curr.child != null) {
386                     stack.push(curr.child);
387                 }
388
389                 curr = curr.right;
390             }
391         }
392
393         buf.append(']');
394
395         return buf.toString();
396     }
397
398     // toString
399
400     /**
401      * Performs a cascading cut operation. This cuts y from its parent and then
402      * does the same for its parent, and so on up the tree.
403      *
404      * <p>Running time: O(log n); O(1) excluding the recursion</p>
405      *
406      * @param y node to perform cascading cut on
407      */
408     protected void cascadingCut(FibonacciHeapNode<T> y)
409     {
410         FibonacciHeapNode<T> z = y.parent;
411
412         // if there's a parent...
413 if (z != null) {
414             // if y is unmarked, set it marked
415 if (!y.mark) {
416                 y.mark = true;
417             } else {
418                 // it's marked, cut it from parent
419 cut(y, z);
420
421                 // cut its parent as well
422 cascadingCut(z);
423             }
424         }
425     }
426
427     // cascadingCut
428
429     /**
430      * Consolidates the trees in the heap by joining trees of equal degree until
431      * there are no more trees of equal degree in the root list.
432      *
433      * <p>Running time: O(log n) amortized</p>
434      */
435     protected void consolidate()
436     {
437         int arraySize = nNodes + 1;
438         List<FibonacciHeapNode<T>> array =
439             new ArrayList<FibonacciHeapNode<T>>(arraySize);
440
441         // Initialize degree array
442 for (int i = 0; i < arraySize; i++) {
443             array.add(null);
444         }
445
446         // Find the number of root nodes.
447 int numRoots = 0;
448         FibonacciHeapNode<T> x = minNode;
449
450         if (x != null) {
451             numRoots++;
452             x = x.right;
453
454             while (x != minNode) {
455                 numRoots++;
456                 x = x.right;
457             }
458         }
459
460         // For each node in root list do...
461 while (numRoots > 0) {
462             // Access this node's degree..
463 int d = x.degree;
464             FibonacciHeapNode<T> next = x.right;
465
466             // ..and see if there's another of the same degree.
467 while (array.get(d) != null) {
468                 // There is, make one of the nodes a child of the other.
469 FibonacciHeapNode<T> y = array.get(d);
470
471                 // Do this based on the key value.
472 if (x.key > y.key) {
473                     FibonacciHeapNode<T> temp = y;
474                     y = x;
475                     x = temp;
476                 }
477
478                 // FibonacciHeapNode<T> y disappears from root list.
479 link(y, x);
480
481                 // We've handled this degree, go to next one.
482 array.set(d, null);
483                 d++;
484             }
485
486             // Save this node for later when we might encounter another
487 // of the same degree.
488 array.set(d, x);
489
490             // Move forward through list.
491 x = next;
492             numRoots--;
493         }
494
495         // Set min to null (effectively losing the root list) and
496 // reconstruct the root list from the array entries in array[].
497 minNode = null;
498
499         for (int i = 0; i < arraySize; i++) {
500             if (array.get(i) != null) {
501                 // We've got a live one, add it to root list.
502 if (minNode != null) {
503                     // First remove node from root list.
504 array.get(i).left.right = array.get(i).right;
505                     array.get(i).right.left = array.get(i).left;
506
507                     // Now add to root list, again.
508 array.get(i).left = minNode;
509                     array.get(i).right = minNode.right;
510                     minNode.right = array.get(i);
511                     array.get(i).right.left = array.get(i);
512
513                     // Check if this is a new min.
514 if (array.get(i).key < minNode.key) {
515                         minNode = array.get(i);
516                     }
517                 } else {
518                     minNode = array.get(i);
519                 }
520             }
521         }
522     }
523
524     // consolidate
525
526     /**
527      * The reverse of the link operation: removes x from the child list of y.
528      * This method assumes that min is non-null.
529      *
530      * <p>Running time: O(1)</p>
531      *
532      * @param x child of y to be removed from y's child list
533      * @param y parent of x about to lose a child
534      */
535     protected void cut(FibonacciHeapNode<T> x, FibonacciHeapNode<T> y)
536     {
537         // remove x from childlist of y and decrement degree[y]
538 x.left.right = x.right;
539         x.right.left = x.left;
540         y.degree--;
541
542         // reset y.child if necessary
543 if (y.child == x) {
544             y.child = x.right;
545         }
546
547         if (y.degree == 0) {
548             y.child = null;
549         }
550
551         // add x to root list of heap
552 x.left = minNode;
553         x.right = minNode.right;
554         minNode.right = x;
555         x.right.left = x;
556
557         // set parent[x] to nil
558 x.parent = null;
559
560         // set mark[x] to false
561 x.mark = false;
562     }
563
564     // cut
565
566     /**
567      * Make node y a child of node x.
568      *
569      * <p>Running time: O(1) actual</p>
570      *
571      * @param y node to become child
572      * @param x node to become parent
573      */
574     protected void link(FibonacciHeapNode<T> y, FibonacciHeapNode<T> x)
575     {
576         // remove y from root list of heap
577 y.left.right = y.right;
578         y.right.left = y.left;
579
580         // make y a child of x
581 y.parent = x;
582
583         if (x.child == null) {
584             x.child = y;
585             y.right = y;
586             y.left = y;
587         } else {
588             y.left = x.child;
589             y.right = x.child.right;
590             x.child.right = y;
591             y.right.left = y;
592         }
593
594         // increase degree[x]
595 x.degree++;
596
597         // set mark[y] false
598 y.mark = false;
599     }
600
601     // link
602 }
603
604 // FibonacciHeap
605
Popular Tags