package DataStructures.Heap;

import DataStructures.Comparable;

import DataStructures.MyInteger;

// PairHeap class

//

// CONSTRUCTION: with no initializer

//

// ******************PUBLIC OPERATIONS*********************

// PairNode insert( x ) --> Insert x, return position

// Comparable deleteMin( )--> Return and remove smallest item

// Comparable findMin( ) --> Return smallest item

// boolean isEmpty( ) --> Return true if empty; else false

// void makeEmpty( ) --> Remove all items

// void decreaseKey( PairNode p, newVal )

// --> Decrease value in node p

/**

* Implements a pairing heap.

* Supports a decreaseKey operation.

* Note that all "matching" is based on the compareTo method.

* @author Mark Allen Weiss

* @see PairNode

*/

public class PairHeap

{

/**

* Construct the pairing heap.

*/

public PairHeap( )

{

root = null;

}

/**

* Insert into the priority queue, and return a PairNode

* that can be used by decreaseKey.

* Duplicates are allowed.

* @param x the item to insert.

* @return the node containing the newly inserted item.

*/

public PairNode insert( Comparable x )

{

PairNode newNode = new PairNode( x );

if( root == null )

root = newNode;

else

root = compareAndLink( root, newNode );

return newNode;

}

/**

* Find the smallest item in the priority queue.

* @return the smallest item, or null if empty.

*/

public Comparable findMin( )

{

if( isEmpty( ) )

return null;

return root.element;

}

/**

* Remove the smallest item from the priority queue.

* @return the smallest item, or null if empty.

*/

public Comparable deleteMin( )

{

if( isEmpty( ) )

return null;

Comparable x = findMin( );

if( root.leftChild == null )

root = null;

else

root = combineSiblings( root.leftChild );

return x;

}

/**

* Change the value of the item stored in the pairing heap.

* Does nothing if newVal is larger than the currently stored value.

* @param p any node returned by addItem.

* @param newVal the new value, which must be smaller

* than the currently stored value.

*/

public void decreaseKey( PairNode p, Comparable newVal )

{

if( p.element.compareTo( newVal ) < 0 )

return; // newVal cannot be bigger

p.element = newVal;

if( p != root )

{

if( p.nextSibling != null )

p.nextSibling.prev = p.prev;

if( p.prev.leftChild == p )

p.prev.leftChild = p.nextSibling;

else

p.prev.nextSibling = p.nextSibling;

p.nextSibling = null;

root = compareAndLink( root, p );

}

}

/**

* Test if the priority queue is logically empty.

* @return true if empty, false otherwise.

*/

public boolean isEmpty( )

{

return root == null;

}

/**

* Make the priority queue logically empty.

*/

public void makeEmpty( )

{

root = null;

}

private PairNode root;

/**

* Internal method that is the basic operation to maintain order.

* Links first and second together to satisfy heap order.

* @param first root of tree 1, which may not be null.

* first.nextSibling MUST be null on entry.

* @param second root of tree 2, which may be null.

* @return result of the tree merge.

*/

private PairNode compareAndLink( PairNode first, PairNode second )

{

if( second == null )

return first;

if( second.element.compareTo( first.element ) < 0 )

{

// Attach first as leftmost child of second

second.prev = first.prev;

first.prev = second;

first.nextSibling = second.leftChild;

if( first.nextSibling != null )

first.nextSibling.prev = first;

second.leftChild = first;

return second;

}

else

{

// Attach second as leftmost child of first

second.prev = first;

first.nextSibling = second.nextSibling;

if( first.nextSibling != null )

first.nextSibling.prev = first;

second.nextSibling = first.leftChild;

if( second.nextSibling != null )

second.nextSibling.prev = second;

first.leftChild = second;

return first;

}

}

private PairNode [ ] doubleIfFull( PairNode [ ] array, int index )

{

if( index == array.length )

{

PairNode [ ] oldArray = array;

array = new PairNode[ index * 2 ];

for( int i = 0; i < index; i++ )

array[ i ] = oldArray[ i ];

}

return array;

}

// The tree array for combineSiblings

private PairNode [ ] treeArray = new PairNode[ 5 ];

/**

* Internal method that implements two-pass merging.

* @param firstSibling the root of the conglomerate;

* assumed not null.

*/

private PairNode combineSiblings( PairNode firstSibling )

{

if( firstSibling.nextSibling == null )

return firstSibling;

// Store the subtrees in an array

int numSiblings = 0;

for( ; firstSibling != null; numSiblings++ )

{

treeArray = doubleIfFull( treeArray, numSiblings );

treeArray[ numSiblings ] = firstSibling;

firstSibling.prev.nextSibling = null; // break links

firstSibling = firstSibling.nextSibling;

}

treeArray = doubleIfFull( treeArray, numSiblings );

treeArray[ numSiblings ] = null;

// Combine subtrees two at a time, going left to right

int i = 0;

for( ; i + 1 < numSiblings; i += 2 )

treeArray[ i ] = compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );

int j = i - 2;

// j has the result of last compareAndLink.

// If an odd number of trees, get the last one.

if( j == numSiblings - 3 )

treeArray[ j ] = compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );

// Now go right to left, merging last tree with

// next to last. The result becomes the new last.

for( ; j >= 2; j -= 2 )

treeArray[ j - 2 ] = compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );

return treeArray[ 0 ];

}

// Test program

public static void main( String [ ] args )

{

PairHeap h = new PairHeap( );

int numItems = 10000;

int i = 37;

int j;

System.out.println( "Checking; no bad output is good" );

for( i = 37; i != 0; i = ( i + 37 ) % numItems )

h.insert( new MyInteger( i ) );

for( i = 1; i < numItems; i++ )

if( ((MyInteger)( h.deleteMin( ) )).intValue( ) != i )

System.out.println( "Oops! " + i );

PairNode [ ] p = new PairNode[ numItems ];

for( i = 0, j = numItems / 2; i < numItems; i++, j =(j+71)%numItems )

p[ j ] = h.insert( new MyInteger( j + numItems ) );

for( i = 0, j = numItems / 2; i < numItems; i++, j =(j+53)%numItems )

h.decreaseKey( p[ j ], new MyInteger(

((MyInteger)p[ j ].element).intValue( ) - numItems ) );

i = -1;

while( !h.isEmpty( ) )

if( ((MyInteger)( h.deleteMin( ) )).intValue( ) != ++i )

System.out.println( "Oops! " + i + " " );

System.out.println( "Check completed" );

}

}