FibonacciHeap


1   /* Copyright (c) 2003 The Nutch Organization.  All rights reserved.   */
2   /* Use subject to the conditions in http://www.nutch.org/LICENSE.txt. */
3   
4   package net.nutch.util;
5   
6   import java.util.Arrays  ;
7   import java.util.HashMap  ;
8   
9   /**
10   * A Fibonacci Heap, as described in <i>Introduction to Algorithms</i> by
11   * Charles E. Leiserson, Thomas H. Cormen, Ronald L. Rivest.
12   *
13   * <p>
14   *
15   * A Fibonacci heap is a very efficient data structure for priority
16   * queuing.  
17   *
18   */
19  public class FibonacciHeap {
20    private FibonacciHeapNode min;
21    private HashMap   itemsToNodes;
22  
23    // private node class
24    private static class FibonacciHeapNode {
25      private Object   userObject;
26      private int priority;
27  
28      private FibonacciHeapNode parent;
29      private FibonacciHeapNode prevSibling;
30      private FibonacciHeapNode nextSibling;
31      private FibonacciHeapNode child;
32      private int degree;
33      private boolean mark;
34  
35      FibonacciHeapNode(Object   userObject, int priority) {
36        this.userObject= userObject;
37        this.priority= priority;
38  
39        this.parent= null;
40        this.prevSibling= this;
41        this.nextSibling= this;
42        this.child= null;
43        this.degree= 0;
44        this.mark= false;
45      }
46  
47      public String   toString() {
48        return "["+userObject+", "+degree+"]";
49      }
50    }
51  
52    /**
53     * Creates a new <code>FibonacciHeap</code>.
54     */
55    public FibonacciHeap() {
56      this.min= null;
57      this.itemsToNodes= new HashMap  ();
58    }
59  
60    /**
61     *  Adds the Object <code>item</code>, with the supplied
62     *  <code>priority</code>.
63     */
64    public void add(Object   item, int priority) {
65      if (itemsToNodes.containsKey(item))
66        throw new IllegalStateException  ("heap already contains item! (item= "
67                                        + item + ")");
68      FibonacciHeapNode newNode= new FibonacciHeapNode(item, priority);
69      itemsToNodes.put(item, newNode);
70  
71      if (min == null) {
72        min= newNode;
73      } else {
74        concatenateSiblings(newNode, min);
75        if (newNode.priority < min.priority) 
76          min= newNode;
77      }
78    }
79  
80    /**
81     * Returns <code>true</code> if <code>item</code> exists in this
82     * <code>FibonacciHeap</code>, false otherwise.
83     */
84    public boolean contains(Object   item) {
85      return itemsToNodes.containsKey(item);
86    }
87  
88    // makes x's nextSibling and prevSibling point to itself
89    private void removeFromSiblings(FibonacciHeapNode x) {
90      if (x.nextSibling == x) 
91        return;
92      x.nextSibling.prevSibling= x.prevSibling;
93      x.prevSibling.nextSibling= x.nextSibling;
94      x.nextSibling= x;
95      x.prevSibling= x;
96    }
97  
98    // joins siblings lists of a and b
99    private void concatenateSiblings(FibonacciHeapNode a, FibonacciHeapNode b) {
100     a.nextSibling.prevSibling= b;
101     b.nextSibling.prevSibling= a;
102     FibonacciHeapNode origAnext= a.nextSibling;
103     a.nextSibling= b.nextSibling;
104     b.nextSibling= origAnext;
105   }
106 
107   /**
108    * Returns the same Object that {@link #popMin()} would, without
109    * removing it.
110    */ 
111   public Object   peekMin() {
112     if (min == null) 
113       return null;
114     return min.userObject;
115   }
116 
117   /**
118    * Returns the number of objects in the heap.
119    */
120   public int size() {
121     return itemsToNodes.size();
122   }
123 
124   /**
125    * Returns the object which has the <em>lowest</em> priority in the
126    * heap.  If the heap is empty, <code>null</code> is returned.
127    */
128   public Object   popMin() {
129     if (min == null) 
130       return null;
131     if (min.child != null) {
132       FibonacciHeapNode tmp= min.child;
133       // rempve parent pointers to min
134       while (tmp.parent != null) {
135         tmp.parent= null;
136         tmp= tmp.nextSibling;
137       }
138       // add children of min to root list
139       concatenateSiblings(tmp, min);
140     }
141     // remove min from root list
142     FibonacciHeapNode oldMin= min;
143     if (min.nextSibling == min) {
144       min= null;
145     } else {
146       min= min.nextSibling;
147       removeFromSiblings(oldMin);
148       consolidate();
149     }
150     itemsToNodes.remove(oldMin.userObject);
151     return oldMin.userObject;
152   }
153 
154   // consolidates heaps of same degree
155   private void consolidate() {
156     int size= size();
157     FibonacciHeapNode[] newRoots= new FibonacciHeapNode[size];
158 
159     FibonacciHeapNode node= min;
160     FibonacciHeapNode start= min;
161     do {
162       FibonacciHeapNode x= node;
163       int currDegree= node.degree;
164       while (newRoots[currDegree] != null) {
165         FibonacciHeapNode y= newRoots[currDegree];
166         if (x.priority > y.priority) {
167           FibonacciHeapNode tmp= x;
168           x= y;
169           y= tmp;
170         }
171         if (y == start) {
172           start= start.nextSibling;
173         }
174         if (y == node) {
175           node= node.prevSibling;
176         }
177         link(y, x);
178         newRoots[currDegree++]= null;
179       }
180       newRoots[currDegree]= x;
181       node= node.nextSibling;
182     } while (node != start);
183 
184     min= null;
185     for (int i= 0; i < newRoots.length; i++) 
186       if (newRoots[i] != null) {
187         if ( (min == null) 
188              || (newRoots[i].priority < min.priority) )
189           min= newRoots[i];
190       }
191   }
192 
193   // links y under x
194   private void link(FibonacciHeapNode y, FibonacciHeapNode x) {
195     removeFromSiblings(y);
196     y.parent= x;
197     if (x.child == null) 
198       x.child= y;
199     else 
200       concatenateSiblings(x.child, y);
201     x.degree++;
202     y.mark= false;
203   }
204 
205   /**
206    * Decreases the <code>priority</code> value associated with
207    * <code>item</code>.
208    *
209    * <p>
210    *
211    * <code>item<code> must exist in the heap, and it's current
212    * priority must be greater than <code>priority</code>.  
213    *
214    * @throws IllegalStateException if <code>item</code> does not exist
215    * in the heap, or if <code>item</code> already has an equal or
216    * lower priority than the supplied<code>priority</code>.
217    */
218   public void decreaseKey(Object   item, int priority) {
219     FibonacciHeapNode node= 
220       (FibonacciHeapNode) itemsToNodes.get(item);
221     if (node == null) 
222       throw new IllegalStateException  ("No such element: " + item);
223     if (node.priority < priority) 
224       throw new IllegalStateException  ("decreaseKey(" + item + ", " 
225                                       + priority + ") called, but priority="
226                                       + node.priority);
227     node.priority= priority;
228     FibonacciHeapNode parent= node.parent;
229     if ( (parent != null) && (node.priority < parent.priority) ) {
230       cut(node, parent);
231       cascadingCut(parent);
232     }
233     if (node.priority < min.priority) 
234       min= node;
235 
236   }
237 
238   // cut node x from below y
239   private void cut(FibonacciHeapNode x, FibonacciHeapNode y) {
240     // remove x from y's children
241     if (y.child == x) 
242       y.child= x.nextSibling;
243     if (y.child == x) 
244       y.child= null;
245 
246     y.degree--;
247     removeFromSiblings(x);
248     concatenateSiblings(x, min);
249     x.parent= null;
250     x.mark= false;
251                 
252   }
253 
254   private void cascadingCut(FibonacciHeapNode y) {
255     FibonacciHeapNode z= y.parent;
256     if (z != null) {
257       if (!y.mark) {
258         y.mark= true;
259       } else {
260         cut(y, z);
261         cascadingCut(z);
262       }
263     }
264   }
265 
266 }
267
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags