Java/Collections Data Structure/Heaps

Материал из Java эксперт
Перейти к: навигация, поиск

Binary Heap Queue

   <source lang="java">
  

/*

* Copyright 2005 JBoss Inc
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
*      http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/

import java.io.Externalizable; import java.io.IOException; import java.io.ObjectInput; import java.io.ObjectOutput; import java.util.ruparator; import java.util.NoSuchElementException; public class BinaryHeapQueue implements Queue, Externalizable {

 /** The default capacity for a binary heap. */
 private final static int DEFAULT_CAPACITY = 13;
 /** The comparator used to order the elements */
 private Comparator comparator;
 /** The number of elements currently in this heap. */
 private int size;
 /** The elements in this heap. */
 private Queueable[] elements;
 public BinaryHeapQueue() {
 }
 /**
  * Constructs a new BinaryHeap that will use the given
  * comparator to order its elements.
  * 
  * @param comparator
  *          the comparator used to order the elements, null means use natural
  *          order
  */
 public BinaryHeapQueue(final Comparator comparator) {
   this(comparator, BinaryHeapQueue.DEFAULT_CAPACITY);
 }
 /**
  * Constructs a new BinaryHeap.
  * 
  * @param comparator
  *          the comparator used to order the elements, null means use natural
  *          order
  * @param capacity
  *          the initial capacity for the heap
  * @throws IllegalArgumentException
  *           if capacity is <= 0
  */
 public BinaryHeapQueue(final Comparator comparator, final int capacity) {
   if (capacity <= 0) {
     throw new IllegalArgumentException("invalid capacity");
   }
   // +1 as 0 is noop
   this.elements = new Queueable[capacity + 1];
   this.ruparator = comparator;
 }
 // -----------------------------------------------------------------------
 public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
   comparator = (Comparator) in.readObject();
   elements = (Queueable[]) in.readObject();
   size = in.readInt();
 }
 public void writeExternal(ObjectOutput out) throws IOException {
   out.writeObject(comparator);
   out.writeObject(elements);
   out.writeInt(size);
 }
 /**
  * Clears all elements from queue.
  */
 public void clear() {
   this.elements = new Queueable[this.elements.length]; // for gc
   this.size = 0;
 }
 /**
  * Tests if queue is empty.
  * 
  * @return true if queue is empty; false
  *         otherwise.
  */
 public boolean isEmpty() {
   return this.size == 0;
 }
 /**
  * Tests if queue is full.
  * 
  * @return true if queue is full; false
  *         otherwise.
  */
 public boolean isFull() {
   // +1 as Queueable 0 is noop
   return this.elements.length == this.size + 1;
 }
 /**
  * Returns the number of elements in this heap.
  * 
  * @return the number of elements in this heap
  */
 public int size() {
   return this.size;
 }
 /**
  * Inserts an Queueable into queue.
  * 
  * @param element
  *          the Queueable to be inserted
  */
 public synchronized void enqueue(final Queueable element) {
   if (isFull()) {
     grow();
   }
   percolateUpMinHeap(element);
 }
 /**
  * Returns the Queueable on top of heap and remove it.
  * 
  * @return the Queueable at top of heap
  * @throws NoSuchElementException
  *           if isEmpty() == true
  */
 public synchronized Queueable dequeue() throws NoSuchElementException {
   if (isEmpty()) {
     return null;
   }
   final Queueable result = this.elements[1];
   result.dequeue();
   // Code bellow was removed because it is already executed
   // inside result.dequeue()
   //
   // setElement(1, this.elements[this.size--]);
   // this.elements[this.size + 1] = null;
   //
   // if (this.size != 0) {
   // percolateDownMinHeap(1);
   // }
   return result;
 }
 /**
  * 
  * @param index
  */
 public synchronized Queueable dequeue(final int index) {
   if (index < 1 || index > this.size) {
     // throw new NoSuchElementException();
     return null;
   }
   final Queueable result = this.elements[index];
   setElement(index, this.elements[this.size]);
   this.elements[this.size] = null;
   this.size--;
   if (this.size != 0 && index <= this.size) {
     int compareToParent = 0;
     if (index > 1) {
       compareToParent = compare(this.elements[index], this.elements[index / 2]);
     }
     if (index > 1 && compareToParent < 0) {
       percolateUpMinHeap(index);
     } else {
       percolateDownMinHeap(index);
     }
   }
   return result;
 }
 /**
  * Percolates Queueable down heap from the position given by the index. <p/>
  * Assumes it is a minimum heap.
  * 
  * @param index
  *          the index for the Queueable
  */
 private void percolateDownMinHeap(final int index) {
   final Queueable element = this.elements[index];
   int hole = index;
   while ((hole * 2) <= this.size) {
     int child = hole * 2;
     // if we have a right child and that child can not be percolated
     // up then move onto other child
     if (child != this.size && compare(this.elements[child + 1], this.elements[child]) < 0) {
       child++;
     }
     // if we found resting place of bubble then terminate search
     if (compare(this.elements[child], element) >= 0) {
       break;
     }
     setElement(hole, this.elements[child]);
     hole = child;
   }
   setElement(hole, element);
 }
 /**
  * Percolates Queueable up heap from the position given by the index. <p/>
  * Assumes it is a minimum heap.
  * 
  * @param index
  *          the index of the Queueable to be percolated up
  */
 private void percolateUpMinHeap(final int index) {
   int hole = index;
   final Queueable element = this.elements[hole];
   while (hole > 1 && compare(element, this.elements[hole / 2]) < 0) {
     // save Queueable that is being pushed down
     // as the Queueable "bubble" is percolated up
     final int next = hole / 2;
     setElement(hole, this.elements[next]);
     hole = next;
   }
   setElement(hole, element);
 }
 /**
  * Percolates a new Queueable up heap from the bottom. <p/> Assumes it is a
  * minimum heap.
  * 
  * @param element
  *          the Queueable
  */
 private void percolateUpMinHeap(final Queueable element) {
   setElement(++this.size, element);
   percolateUpMinHeap(this.size);
 }
 /**
  * Compares two objects using the comparator if specified, or the natural
  * order otherwise.
  * 
  * @param a
  *          the first object
  * @param b
  *          the second object
  * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
  */
 private int compare(final Queueable a, final Queueable b) {
   return this.ruparator.rupare(a, b);
 }
 /**
  * Increases the size of the heap to support additional elements
  */
 private void grow() {
   final Queueable[] elements = new Queueable[this.elements.length * 2];
   System.arraycopy(this.elements, 0, elements, 0, this.elements.length);
   this.elements = elements;
 }
 /**
  * 
  * @param index
  * @param element
  */
 private void setElement(final int index, final Queueable element) {
   this.elements[index] = element;
   element.enqueued(this, index);
 }
 public Queueable[] getQueueable() {
   return this.elements;
 }
 public Object[] toArray() {
   final Object[] result = new Object[this.size];
   System.arraycopy(this.elements, 1, result, 0, this.size);
   return result;
 }
 public Object[] toArray(Object a[]) {
   if (a.length < this.size) {
     a = (Object[]) java.lang.reflect.Array
         .newInstance(a.getClass().getComponentType(), this.size);
   }
   System.arraycopy(this.elements, 1, a, 0, this.size);
   if (a.length > this.size) {
     a[this.size] = null;
   }
   return a;
 }

} /*

* Copyright 2005 JBoss Inc
* 
* Licensed under the Apache License, Version 2.0 (the "License"); you may not
* use this file except in compliance with the License. You may obtain a copy of
* the License at
* 
* http://www.apache.org/licenses/LICENSE-2.0
* 
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
* License for the specific language governing permissions and limitations under
* the License.
*/

interface Queue {

 public void enqueue(Queueable queueable);
 public Queueable dequeue();
 public Queueable dequeue(int index);
 public boolean isEmpty();

} /*

* Copyright 2005 JBoss Inc
* 
* Licensed under the Apache License, Version 2.0 (the "License"); you may not
* use this file except in compliance with the License. You may obtain a copy of
* the License at
* 
* http://www.apache.org/licenses/LICENSE-2.0
* 
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
* License for the specific language governing permissions and limitations under
* the License.
*/

interface Queueable {

 public void enqueued(Queue queue, int index);
 public void dequeue();

}


 </source>
   
  
 
  



Demonstrates heaps

   <source lang="java">
 

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

public class Heap {

 private Node[] heapArray;
 private int maxSize; // size of array
 private int currentSize; // number of nodes in array
 public Heap(int mx) {
   maxSize = mx;
   currentSize = 0;
   heapArray = new Node[maxSize]; // create array
 }
 public boolean isEmpty() {
   return currentSize == 0;
 }
 public boolean insert(int key) {
   if (currentSize == maxSize)
     return false;
   Node newNode = new Node(key);
   heapArray[currentSize] = newNode;
   trickleUp(currentSize++);
   return true;
 } 
 public void trickleUp(int index) {
   int parent = (index - 1) / 2;
   Node bottom = heapArray[index];
   while (index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
     heapArray[index] = heapArray[parent]; // move it down
     index = parent;
     parent = (parent - 1) / 2;
   }
   heapArray[index] = bottom;
 }
 public Node remove() // delete item with max key
 { // (assumes non-empty list)
   Node root = heapArray[0];
   heapArray[0] = heapArray[--currentSize];
   trickleDown(0);
   return root;
 } // end remove()
 public void trickleDown(int index) {
   int largerChild;
   Node top = heapArray[index]; // save root
   while (index < currentSize / 2) // while node has at
   { //    least one child,
     int leftChild = 2 * index + 1;
     int rightChild = leftChild + 1;
     // find larger child
     if (rightChild < currentSize
         && // (rightChild exists?)
         heapArray[leftChild].getKey() < heapArray[rightChild]
             .getKey())
       largerChild = rightChild;
     else
       largerChild = leftChild;
     // top >= largerChild?
     if (top.getKey() >= heapArray[largerChild].getKey())
       break;
     // shift child up
     heapArray[index] = heapArray[largerChild];
     index = largerChild; // go down
   }
   heapArray[index] = top; // root to index
 }
 public boolean change(int index, int newValue) {
   if (index < 0 || index >= currentSize)
     return false;
   int oldValue = heapArray[index].getKey(); // remember old
   heapArray[index].setKey(newValue); // change to new
   if (oldValue < newValue) 
     trickleUp(index); 
   else
     trickleDown(index);
   return true;
 }
 public void displayHeap() {
   System.out.print("heapArray: "); // array format
   for (int m = 0; m < currentSize; m++)
     if (heapArray[m] != null)
       System.out.print(heapArray[m].getKey() + " ");
     else
       System.out.print("-- ");
   int nBlanks = 32;
   int itemsPerRow = 1;
   int column = 0;
   int j = 0; // current item
   while (currentSize > 0) // for each heap item
   {
     if (column == 0) // first item in row?
       for (int k = 0; k < nBlanks; k++)
         // preceding blanks
         System.out.print(" ");
     // display item
     System.out.print(heapArray[j].getKey());
     if (++j == currentSize) // done?
       break;
     if (++column == itemsPerRow) // end of row?
     {
       nBlanks /= 2; // half the blanks
       itemsPerRow *= 2; // twice the items
       column = 0; // start over on
       System.out.println(); //    new row
     } else
       // next item on row
       for (int k = 0; k < nBlanks * 2 - 2; k++)
         System.out.print(" "); // interim blanks
   } 
 }
 public static void main(String[] args) throws IOException {
   int value, value2;
   Heap h = new Heap(31); // make a Heap; max size 31
   boolean success;
   h.insert(70); // insert 10 items
   h.insert(40);
   h.insert(50);
   h.insert(20);
   h.insert(60);
   h.insert(100);
   h.insert(80);
   h.insert(30);
   h.insert(10);
   h.insert(90);
   h.displayHeap();
   value = 100;
   success = h.insert(value);
   if (!success)
     System.out.println("Can"t insert; heap full");
   if (!h.isEmpty())
     h.remove();
   else
     System.out.println("Can"t remove; heap empty");
   value = 80;
   value2 = 999;
   success = h.change(value, value2);
   if (!success)
     System.out.println("Invalid index");
 }
 class Node {
   private int data; 
   public Node(int key) {
     data = key;
   }
   public int getKey() {
     return data;
   }
   public void setKey(int id) {
     data = id;
   }
 }

}


 </source>
   
  
 
  



Fibonacci heap data structure

   <source lang="java">
  

/*

* JGraphT : a free Java graph-theory library
* 
*
* Project Info:  http://jgrapht.sourceforge.net/
* Project Creator:  Barak Naveh (barak_naveh@users.sourceforge.net)
*
* (C) Copyright 2003-2007, by Barak Naveh and Contributors.
*
* This library is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or
* (at your option) any later version.
*
* This library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library; if not, write to the Free Software Foundation,
* Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
*/

/* --------------------------

* FibonnaciHeap.java
* --------------------------
* (C) Copyright 1999-2003, by Nathan Fiedler and Contributors.
*
* Original Author:  Nathan Fiedler
* Contributor(s):   John V. Sichi
*
* $Id: FibonacciHeap.java 603 2008-06-28 07:51:50Z perfecthash $
*
* Changes
* -------
* 03-Sept-2003 : Adapted from Nathan Fiedler (JVS);
*
*      Name    Date            Description
*      ----    ----            -----------
*      nf      08/31/97        Initial version
*      nf      09/07/97        Removed FibHeapData interface
*      nf      01/20/01        Added synchronization
*      nf      01/21/01        Made Node an inner class
*      nf      01/05/02        Added clear(), renamed empty() to
*                              isEmpty(), and renamed printHeap()
*                              to toString()
*      nf      01/06/02        Removed all synchronization
*
*/

import java.util.*;

/**

* This class implements a Fibonacci heap data structure. Much of the code in
* this class is based on the algorithms in the "Introduction to Algorithms"by
* Cormen, Leiserson, and Rivest in Chapter 21. The amortized running time of
* most of these methods is O(1), making it a very fast data structure. Several
* have an actual running time of O(1). removeMin() and delete() have O(log n)
* amortized running times because they do the heap consolidation. If you
* attempt to store nodes in this heap with key values of -Infinity
* (Double.NEGATIVE_INFINITY) the delete() operation may fail to
* remove the correct element.
*
*

Note that this implementation is not synchronized. If multiple * threads access a set concurrently, and at least one of the threads modifies * the set, it must be synchronized externally. This is typically * accomplished by synchronizing on some object that naturally encapsulates the * set.

*
*

This class was originally developed by Nathan Fiedler for the GraphMaker * project. It was imported to JGraphT with permission, courtesy of Nathan * Fiedler.

*
* @author Nathan Fiedler
*/

public class FibonacciHeap<T> {

   //~ Static fields/initializers ---------------------------------------------
   private static final double oneOverLogPhi =
       1.0 / Math.log((1.0 + Math.sqrt(5.0)) / 2.0);
   //~ Instance fields --------------------------------------------------------
   /**
    * Points to the minimum node in the heap.
    */
   private FibonacciHeapNode<T> minNode;
   /**
    * Number of nodes in the heap.
    */
   private int nNodes;
   //~ Constructors -----------------------------------------------------------
   /**
    * Constructs a FibonacciHeap object that contains no elements.
    */
   public FibonacciHeap()
   {
   } // FibonacciHeap
   //~ Methods ----------------------------------------------------------------
   /**
    * Tests if the Fibonacci heap is empty or not. Returns true if the heap is
    * empty, false otherwise.
    *
*

Running time: O(1) actual

    *
    * @return true if the heap is empty, false otherwise
    */
   public boolean isEmpty()
   {
       return minNode == null;
   }
   // isEmpty
   /**
    * Removes all elements from this heap.
    */
   public void clear()
   {
       minNode = null;
       nNodes = 0;
   }
   // clear
   /**
    * Decreases the key value for a heap node, given the new value to take on.
    * The structure of the heap may be changed and will not be consolidated.
    *
*

Running time: O(1) amortized

    *
    * @param x node to decrease the key of
    * @param k new key value for node x
    *
    * @exception IllegalArgumentException Thrown if k is larger than x.key
    * value.
    */
   public void decreaseKey(FibonacciHeapNode<T> x, double k)
   {
       if (k > x.key) {
           throw new IllegalArgumentException(
               "decreaseKey() got larger key value");
       }
       x.key = k;
       FibonacciHeapNode<T> y = x.parent;
       if ((y != null) && (x.key < y.key)) {
           cut(x, y);
           cascadingCut(y);
       }
       if (x.key < minNode.key) {
           minNode = x;
       }
   }
   // decreaseKey
   /**
    * Deletes a node from the heap given the reference to the node. The trees
    * in the heap will be consolidated, if necessary. This operation may fail
    * to remove the correct element if there are nodes with key value
    * -Infinity.
    *
*

Running time: O(log n) amortized

    *
    * @param x node to remove from heap
    */
   public void delete(FibonacciHeapNode<T> x)
   {
       // make x as small as possible
       decreaseKey(x, Double.NEGATIVE_INFINITY);
       // remove the smallest, which decreases n also
       removeMin();
   }
   // delete
   /**
    * Inserts a new data element into the heap. No heap consolidation is
    * performed at this time, the new node is simply inserted into the root
    * list of this heap.
    *
*

Running time: O(1) actual

    *
    * @param node new node to insert into heap
    * @param key key value associated with data object
    */
   public void insert(FibonacciHeapNode<T> node, double key)
   {
       node.key = key;
       // concatenate node into min list
       if (minNode != null) {
           node.left = minNode;
           node.right = minNode.right;
           minNode.right = node;
           node.right.left = node;
           if (key < minNode.key) {
               minNode = node;
           }
       } else {
           minNode = node;
       }
       nNodes++;
   }
   // insert
   /**
    * Returns the smallest element in the heap. This smallest element is the
    * one with the minimum key value.
    *
*

Running time: O(1) actual

    *
    * @return heap node with the smallest key
    */
   public FibonacciHeapNode<T> min()
   {
       return minNode;
   }
   // min
   /**
    * Removes the smallest element from the heap. This will cause the trees in
    * the heap to be consolidated, if necessary.
    *
*

Running time: O(log n) amortized

    *
    * @return node with the smallest key
    */
   public FibonacciHeapNode<T> removeMin()
   {
       FibonacciHeapNode<T> z = minNode;
       if (z != null) {
           int numKids = z.degree;
           FibonacciHeapNode<T> x = z.child;
           FibonacciHeapNode<T> tempRight;
           // for each child of z do...
           while (numKids > 0) {
               tempRight = x.right;
               // remove x from child list
               x.left.right = x.right;
               x.right.left = x.left;
               // add x to root list of heap
               x.left = minNode;
               x.right = minNode.right;
               minNode.right = x;
               x.right.left = x;
               // set parent[x] to null
               x.parent = null;
               x = tempRight;
               numKids--;
           }
           // remove z from root list of heap
           z.left.right = z.right;
           z.right.left = z.left;
           if (z == z.right) {
               minNode = null;
           } else {
               minNode = z.right;
               consolidate();
           }
           // decrement size of heap
           nNodes--;
       }
       return z;
   }
   // removeMin
   /**
    * Returns the size of the heap which is measured in the number of elements
    * contained in the heap.
    *
*

Running time: O(1) actual

    *
    * @return number of elements in the heap
    */
   public int size()
   {
       return nNodes;
   }
   // size
   /**
    * Joins two Fibonacci heaps into a new one. No heap consolidation is
    * performed at this time. The two root lists are simply joined together.
    *
*

Running time: O(1) actual

    *
    * @param h1 first heap
    * @param h2 second heap
    *
    * @return new heap containing h1 and h2
    */
   public static <T> FibonacciHeap<T> union(
       FibonacciHeap<T> h1,
       FibonacciHeap<T> h2)
   {
       FibonacciHeap<T> h = new FibonacciHeap<T>();
       if ((h1 != null) && (h2 != null)) {
           h.minNode = h1.minNode;
           if (h.minNode != null) {
               if (h2.minNode != null) {
                   h.minNode.right.left = h2.minNode.left;
                   h2.minNode.left.right = h.minNode.right;
                   h.minNode.right = h2.minNode;
                   h2.minNode.left = h.minNode;
                   if (h2.minNode.key < h1.minNode.key) {
                       h.minNode = h2.minNode;
                   }
               }
           } else {
               h.minNode = h2.minNode;
           }
           h.nNodes = h1.nNodes + h2.nNodes;
       }
       return h;
   }
   // union
   /**
    * Creates a String representation of this Fibonacci heap.
    *
    * @return String of this.
    */
   public String toString()
   {
       if (minNode == null) {
           return "FibonacciHeap=[]";
       }
       // create a new stack and put root on it
       Stack<FibonacciHeapNode<T>> stack = new Stack<FibonacciHeapNode<T>>();
       stack.push(minNode);
       StringBuffer buf = new StringBuffer(512);
       buf.append("FibonacciHeap=[");
       // do a simple breadth-first traversal on the tree
       while (!stack.empty()) {
           FibonacciHeapNode<T> curr = stack.pop();
           buf.append(curr);
           buf.append(", ");
           if (curr.child != null) {
               stack.push(curr.child);
           }
           FibonacciHeapNode<T> start = curr;
           curr = curr.right;
           while (curr != start) {
               buf.append(curr);
               buf.append(", ");
               if (curr.child != null) {
                   stack.push(curr.child);
               }
               curr = curr.right;
           }
       }
       buf.append("]");
       return buf.toString();
   }
   // toString
   /**
    * Performs a cascading cut operation. This cuts y from its parent and then
    * does the same for its parent, and so on up the tree.
    *
*

Running time: O(log n); O(1) excluding the recursion

    *
    * @param y node to perform cascading cut on
    */
   protected void cascadingCut(FibonacciHeapNode<T> y)
   {
       FibonacciHeapNode<T> z = y.parent;
       // if there"s a parent...
       if (z != null) {
           // if y is unmarked, set it marked
           if (!y.mark) {
               y.mark = true;
           } else {
               // it"s marked, cut it from parent
               cut(y, z);
               // cut its parent as well
               cascadingCut(z);
           }
       }
   }
   // cascadingCut
   protected void consolidate()
   {
       int arraySize =
           ((int) Math.floor(Math.log(nNodes) * oneOverLogPhi)) + 1;
       List<FibonacciHeapNode<T>> array =
           new ArrayList<FibonacciHeapNode<T>>(arraySize);
       // Initialize degree array
       for (int i = 0; i < arraySize; i++) {
           array.add(null);
       }
       // Find the number of root nodes.
       int numRoots = 0;
       FibonacciHeapNode<T> x = minNode;
       if (x != null) {
           numRoots++;
           x = x.right;
           while (x != minNode) {
               numRoots++;
               x = x.right;
           }
       }
       // For each node in root list do...
       while (numRoots > 0) {
           // Access this node"s degree..
           int d = x.degree;
           FibonacciHeapNode<T> next = x.right;
           // ..and see if there"s another of the same degree.
           for (;;) {
               FibonacciHeapNode<T> y = array.get(d);
               if (y == null) {
                   // Nope.
                   break;
               }
               // There is, make one of the nodes a child of the other.
               // Do this based on the key value.
               if (x.key > y.key) {
                   FibonacciHeapNode<T> temp = y;
                   y = x;
                   x = temp;
               }
               // FibonacciHeapNode<T> y disappears from root list.
               link(y, x);
               // We"ve handled this degree, go to next one.
               array.set(d, null);
               d++;
           }
           // Save this node for later when we might encounter another
           // of the same degree.
           array.set(d, x);
           // Move forward through list.
           x = next;
           numRoots--;
       }
       // Set min to null (effectively losing the root list) and
       // reconstruct the root list from the array entries in array[].
       minNode = null;
       for (int i = 0; i < arraySize; i++) {
           FibonacciHeapNode<T> y = array.get(i);
           if (y == null) {
               continue;
           }
           // We"ve got a live one, add it to root list.
           if (minNode != null) {
               // First remove node from root list.
               y.left.right = y.right;
               y.right.left = y.left;
               // Now add to root list, again.
               y.left = minNode;
               y.right = minNode.right;
               minNode.right = y;
               y.right.left = y;
               // Check if this is a new min.
               if (y.key < minNode.key) {
                   minNode = y;
               }
           } else {
               minNode = y;
           }
       }
   }
   // consolidate
   /**
    * The reverse of the link operation: removes x from the child list of y.
    * This method assumes that min is non-null.
    *
*

Running time: O(1)

    *
    * @param x child of y to be removed from y"s child list
    * @param y parent of x about to lose a child
    */
   protected void cut(FibonacciHeapNode<T> x, FibonacciHeapNode<T> y)
   {
       // remove x from childlist of y and decrement degree[y]
       x.left.right = x.right;
       x.right.left = x.left;
       y.degree--;
       // reset y.child if necessary
       if (y.child == x) {
           y.child = x.right;
       }
       if (y.degree == 0) {
           y.child = null;
       }
       // add x to root list of heap
       x.left = minNode;
       x.right = minNode.right;
       minNode.right = x;
       x.right.left = x;
       // set parent[x] to nil
       x.parent = null;
       // set mark[x] to false
       x.mark = false;
   }
   // cut
   /**
    * Make node y a child of node x.
    *
*

Running time: O(1) actual

    *
    * @param y node to become child
    * @param x node to become parent
    */
   protected void link(FibonacciHeapNode<T> y, FibonacciHeapNode<T> x)
   {
       // remove y from root list of heap
       y.left.right = y.right;
       y.right.left = y.left;
       // make y a child of x
       y.parent = x;
       if (x.child == null) {
           x.child = y;
           y.right = y;
           y.left = y;
       } else {
           y.left = x.child;
           y.right = x.child.right;
           x.child.right = y;
           y.right.left = y;
       }
       // increase degree[x]
       x.degree++;
       // set mark[y] false
       y.mark = false;
   }
   // link

} // FibonacciHeap /*

* JGraphT : a free Java graph-theory library
* 
*
* Project Info:  http://jgrapht.sourceforge.net/
* Project Creator:  Barak Naveh (barak_naveh@users.sourceforge.net)
*
* (C) Copyright 2003-2007, by Barak Naveh and Contributors.
*
* This library is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or
* (at your option) any later version.
*
* This library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library; if not, write to the Free Software Foundation,
* Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
*/

/* --------------------------

* FibonnaciHeapNode.java
* --------------------------
* (C) Copyright 1999-2007, by Nathan Fiedler and Contributors.
*
* Original Author:  Nathan Fiedler
* Contributor(s):   John V. Sichi
*
* $Id: FibonacciHeapNode.java 568 2007-09-30 00:12:18Z perfecthash $
*
* Changes
* -------
* 03-Sept-2003 : Adapted from Nathan Fiedler (JVS);
*
*      Name    Date            Description
*      ----    ----            -----------
*      nf      08/31/97        Initial version
*      nf      09/07/97        Removed FibHeapData interface
*      nf      01/20/01        Added synchronization
*      nf      01/21/01        Made Node an inner class
*      nf      01/05/02        Added clear(), renamed empty() to
*                              isEmpty(), and renamed printHeap()
*                              to toString()
*      nf      01/06/02        Removed all synchronization
*      JVS     06/24/06        Generics
*
*/

/**

* Implements a node of the Fibonacci heap. It holds the information necessary
* for maintaining the structure of the heap. It also holds the reference to the
* key value (which is used to determine the heap structure).
*
* @author Nathan Fiedler
*/

class FibonacciHeapNode<T> {

   //~ Instance fields --------------------------------------------------------
   /**
    * Node data.
    */
   T data;
   /**
    * first child node
    */
   FibonacciHeapNode<T> child;
   /**
    * left sibling node
    */
   FibonacciHeapNode<T> left;
   /**
    * parent node
    */
   FibonacciHeapNode<T> parent;
   /**
    * right sibling node
    */
   FibonacciHeapNode<T> right;
   /**
    * true if this node has had a child removed since this node was added to
    * its parent
    */
   boolean mark;
   /**
    * key value for this node
    */
   double key;
   /**
    * number of children of this node (does not count grandchildren)
    */
   int degree;
   //~ Constructors -----------------------------------------------------------
   /**
    * Default constructor. Initializes the right and left pointers, making this
    * a circular doubly-linked list.
    *
    * @param data data for this node
    * @param key initial key for node
    */
   public FibonacciHeapNode(T data, double key)
   {
       right = this;
       left = this;
       this.data = data;
       this.key = key;
   }
   //~ Methods ----------------------------------------------------------------
   /**
    * Obtain the key for this node.
    *
    * @return the key
    */
   public final double getKey()
   {
       return key;
   }
   /**
    * Obtain the data for this node.
    */
   public final T getData()
   {
       return data;
   }
   /**
    * Return the string representation of this object.
    *
    * @return string representing this object
    */
   public String toString()
   {
       if (true) {
           return Double.toString(key);
       } else {
           StringBuffer buf = new StringBuffer();
           buf.append("Node=[parent = ");
           if (parent != null) {
               buf.append(Double.toString(parent.key));
           } else {
               buf.append("---");
           }
           buf.append(", key = ");
           buf.append(Double.toString(key));
           buf.append(", degree = ");
           buf.append(Integer.toString(degree));
           buf.append(", right = ");
           if (right != null) {
               buf.append(Double.toString(right.key));
           } else {
               buf.append("---");
           }
           buf.append(", left = ");
           if (left != null) {
               buf.append(Double.toString(left.key));
           } else {
               buf.append("---");
           }
           buf.append(", child = ");
           if (child != null) {
               buf.append(Double.toString(child.key));
           } else {
               buf.append("---");
           }
           buf.append("]");
           return buf.toString();
       }
   }
   // toString

} // End FibonacciHeapNode.java


 </source>