Java/Collections Data Structure/Heaps
Версия от 18:01, 31 мая 2010; (обсуждение)
Binary Heap Queue
/*
* 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 <code>BinaryHeap</code> 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 <code>BinaryHeap</code>.
*
* @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 <code>capacity</code> is <= <code>0</code>
*/
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 <code>true</code> if queue is empty; <code>false</code>
* otherwise.
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* Tests if queue is full.
*
* @return <code>true</code> if queue is full; <code>false</code>
* 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 <code>isEmpty() == true</code>
*/
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();
}
Demonstrates heaps
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;
}
}
}
Fibonacci heap data structure
/*
* 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 <code>delete()</code> operation may fail to
* remove the correct element.
*
* <p><b>Note that this implementation is not synchronized.</b> If multiple
* threads access a set concurrently, and at least one of the threads modifies
* the set, it <i>must</i> be synchronized externally. This is typically
* accomplished by synchronizing on some object that naturally encapsulates the
* set.</p>
*
* <p>This class was originally developed by Nathan Fiedler for the GraphMaker
* project. It was imported to JGraphT with permission, courtesy of Nathan
* Fiedler.</p>
*
* @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.
*
* <p>Running time: O(1) actual</p>
*
* @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.
*
* <p>Running time: O(1) amortized</p>
*
* @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.
*
* <p>Running time: O(log n) amortized</p>
*
* @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.
*
* <p>Running time: O(1) actual</p>
*
* @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.
*
* <p>Running time: O(1) actual</p>
*
* @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.
*
* <p>Running time: O(log n) amortized</p>
*
* @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.
*
* <p>Running time: O(1) actual</p>
*
* @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.
*
* <p>Running time: O(1) actual</p>
*
* @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.
*
* <p>Running time: O(log n); O(1) excluding the recursion</p>
*
* @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.
*
* <p>Running time: O(1)</p>
*
* @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.
*
* <p>Running time: O(1) actual</p>
*
* @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
