Java/Collections Data Structure/Heaps
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 newBinaryHeap
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 newBinaryHeap
. * * @param comparator * the comparator used to order the elements, null means use natural * order * @param capacity * the initial capacity for the heap * @throws IllegalArgumentException * ifcapacity
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. * * @returntrue
if queue is empty;false
* otherwise. */ public boolean isEmpty() { return this.size == 0; } /** * Tests if queue is full. * * @returntrue
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 * ifisEmpty() == 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>