You might want to post the two bits of code (Java/C++) ?
I received permission to post the Java code. Let’s just say that the C++ code looks mostly the same. It goes without saying that my company reserves the copyright to this code, so you should avoid copying it.
A couple of notes. 1) I extracted comments - code was too long for the board 2) Don’t worry about the asserts 3) Performance numbers came from running inserts and extractMins a million times and taking average. Best times are with -server and sufficient heap (i.e. 256M). Tests took place on a 2.4GHZ PIV with 512M.
Thanks and God bless,
-Toby Reyelts
import java.util.*;
/**
* A FibonacciHeap specialized for keys of type int.
*
* Copyright SSA Global 12/10/2003
*
* @author Toby Reyelts
*
*/
public class IntFibonacciHeap<V> {
// Used in max degree calculations
private static final double PHI = ( 1.0d + Math.sqrt( 5 ) ) / 2.0d;
private static final double LOG_PHI = Math.log( PHI );
private Node<V> min; // Both the minimum node and the pointer to the root list
private int size; // The total number of nodes in the tree
// Performance statistics
private double totalInsertTime;
private double totalDecreaseKeyTime;
private double totalExtractMinTime;
private double totalInsertCalls;
private double totalDecreaseKeyCalls;
private double totalExtractMinCalls;
private double largestSize;
public IntFibonacciHeap() {}
public static class Node<V> {
public Node( int key, V value ) {
assert( key >= 0 );
this.key = key;
this.value = value;
right = this;
left = this;
}
private int degree;
private Node<V> parent;
private Node<V> child; // only valid when degree is > 0
private Node<V> right;
private Node<V> left;
private boolean mark;
private boolean deleted;
private int key;
protected V value;
public int key() {
return key;
}
public V value() {
return value;
}
public V setValue( V value ) {
V temp = this.value;
this.value = value;
return temp;
}
public String toString() {
return key + "";
}
public String debugString() {
return key + " parent: " + parent + " right: " + right + " left: " + left + " degree: " + degree + " child: " + child;
}
}
public void insert( Node<V> node ) {
assert( ! node.deleted );
++totalInsertCalls;
assert( node != null );
assertNullParents();
assert( node.parent == null );
assert( node.child == null );
assert( node.right == node );
assert( node.left == node );
assert( node.mark == false );
assert( node.degree == 0 );
if ( min == null ) {
min = node;
++size;
return;
}
// Insert the new node
node.left = min;
node.right = min.right;
min.right.left = node;
min.right = node;
// Update the minimum if necessary
if ( node.key < min.key ) {
min = node;
}
++size;
assertNullParents();
}
public Node<V> min() {
return min;
}
public Node<V> extractMin() {
++totalExtractMinCalls;
if ( min == null ) {
return null;
}
assertNullParents();
Node<V> child = min.child;
Node<V> currentMin = min;
if ( min.degree > 0 ) {
for ( int i = 0; i < min.degree; ++i ) {
child.parent = null;
child = child.right;
}
min.degree = 0;
min.child = null;
Node<V> rightOfMin = min.right;
Node<V> leftOfChild = child.left;
min.right = child;
child.left = min;
leftOfChild.right = rightOfMin;
rightOfMin.left = leftOfChild;
}
if ( size == 1 ) {
min = null;
}
else {
min.right.left = min.left;
min.left.right = min.right;
min = min.right; // pick an arbitrary min - we have to recalculate it anyway
consolidate();
}
--size;
assertNullParents();
currentMin.deleted = true;
return currentMin;
}
public int size() {
assert( size >= 0 );
return size;
}
private void assertNullParents() {
/*
int i = 0;
if ( min == null ) {
return;
}
Node<V> temp = min;
do {
assert( temp.parent == null );
temp = temp.right;
++i;
assert( i <= size );
}
while ( temp != min );
*/
}
private void consolidate() {
assert( min != null );
assert( min.parent == null );
assertNullParents();
int largestDegree = ( int ) Math.floor( Math.log( size ) / LOG_PHI );
Node[] nodes = new Node[ largestDegree + 1 ];
Node<V> x = min;
while ( true ) {
Node<V> current = x;
assert( current.parent == null );
Node<V> next = x.right;
x.right.left = x.left;
x.left.right = x.right;
x.right = x;
x.left = x;
int degree = x.degree;
while ( true ) {
Node<V> y = ( Node<V> ) nodes[ degree ];
if ( y == null ) {
break;
}
assert( y.parent == null );
if ( x.key > y.key ) {
Node<V> temp = x;
x = y;
y = temp;
}
link( y, x );
assert( x.parent == null );
nodes[ degree ] = null;
++degree;
}
assert( x.parent == null );
nodes[ degree ] = x;
if ( next == current ) {
break;
}
x = next;
}
min = null;
int length = nodes.length;
for ( int i = 0; i < length; ++i ) {
Node<V> node = nodes[ i ];
if ( node != null ) {
assert( node.parent == null );
if ( min == null ) {
min = node;
continue;
}
node.left = min;
node.right = min.right;
min.right.left = node;
min.right = node;
if ( node.key < min.key ) {
min = node;
}
}
}
}
private void link( Node<V> y, Node<V> x ) {
assert( y != null );
assert( x != null );
assert( y.parent == null );
assert( x.parent == null );
y.parent = x;
if ( x.degree == 0 ) {
x.child = y;
y.right = y;
y.left = y;
}
else {
y.left = x.child;
y.right = x.child.right;
x.child.right.left = y;
x.child.right = y;
}
++x.degree;
y.mark = false;
}
public void decreaseKey( Node<V> node, int key ) {
assert ( ! node.deleted );
++totalDecreaseKeyCalls;
assert( node.key >= key );
assertNullParents();
node.key = key;
Node<V> parent = node.parent;
if ( parent != null && ( key < parent.key ) ) {
cut( node, parent );
cascadingCut( parent );
}
if ( key < min.key ) {
min = node;
}
assertNullParents();
}
public void delete( Node<V> node ) {
assert ( ! node.deleted );
assertNullParents();
Node<V> parent = node.parent;
if ( parent != null ) {
cut( node, parent );
cascadingCut( parent );
}
min = node;
extractMin();
assertNullParents();
}
private void cut( Node<V> child, Node<V> parent ) {
assertNullParents();
child.parent = null;
--parent.degree;
if ( parent.degree == 0 ) {
parent.child = null;
}
else {
parent.child = child.right;
child.right.left = child.left;
child.left.right = child.right;
}
child.left = min;
child.right = min.right;
min.right.left = child;
min.right = child;
child.mark = false;
assertNullParents();
}
private void cascadingCut( Node<V> node ) {
Node<V> parent = node.parent;
if ( parent == null ) {
return;
}
if ( ! node.mark ) {
node.mark = true;
}
else {
cut( node, parent );
cascadingCut( parent );
}
}
public void print( Node<V> node, boolean debug ) {
if ( node == null ) {
return;
}
Node<V> begin = node;
Node<V> current = node;
while ( true ) {
if ( debug ) {
System.out.println( current.debugString() );
}
else {
System.out.println( current );
}
if ( current.degree > 0 ) {
print( current.child, debug );
}
current = current.right;
if ( current == begin ) {
return;
}
}
}
public void print( boolean debug ) {
print( min, debug );
}
public double totalInsertTime() {
return totalInsertTime;
}
public double totalExtractMinTime() {
return totalExtractMinTime;
}
public double totalDecreaseKeyTime() {
return totalDecreaseKeyTime;
}
public double totalInsertCalls() {
return totalInsertCalls;
}
public double totalExtractMinCalls() {
return totalExtractMinCalls;
}
public double totalDecreaseKeyCalls() {
return totalDecreaseKeyCalls;
}
public double largestSize() {
return largestSize;
}
public static void main( String[] args ) {
IntFibonacciHeap<String> heap = new IntFibonacciHeap<String>();
int[] ints = new int[] { 23, 7, 3, 3, 3, 14, 14, 7, 17, 30, 24, 26, 46, 35 };
Node[] nodes = new Node[ ints.length ];
for ( int i = 0; i < ints.length; ++i ) {
Node<String> node = new Node<String>( ints[ i ], "" + i );
heap.insert( node );
nodes[ i ] = node;
}
while ( heap.size() > 0 ) {
System.out.println( "Heap min: " + heap.extractMin() );
}
}
}
