I have an assignment in my Data Structure class that is giving me problems. The instructor wants us to modify existing code for a binary heap class that uses an array implementation and convert it to using binary nodes instead. I added a binary node inner class and modified the constructors with links to the parent, left and right children, and left and right sibling. I am not sure if I need all those links. I also added some print methods and height method so I could do a little testing.
My first inclination was to convert the insert method. I really am stuck on how to do this assignment. I know that I should traverse down the left side of the heap and then travel right side to the next available slot.
--------x
-------x x
------x x x
----x x
I have had trouble doing both of the traversals and getting the correct placement of the node ( next node 10 should go to right of 9 on bottom row). All of this has to be done before I can percolate up the node to the correct spot. Any coding ideas would be very helpful. If someone can help me with the insert method ( including the percolate up function), I am pretty sure I can figure out how to convert the other methods.
// BinaryHeap class
//
// CONSTRUCTION: with optional capacity (that defaults to 100)
// or an array containing initial items
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// 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
// ******************ERRORS********************************
// Throws UnderflowException as appropriate
/**
* Implements a binary heap.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class BinaryHeapwBinaryTree<AnyType extends Comparable<? super AnyType>>
{
private BinaryNode<AnyType> root;
private int numElements;
private int rowNumber;
private static int nodeNumber;
/**
* Construct the binary heap.
*/
public BinaryHeapwBinaryTree( )
{
//this( DEFAULT_CAPACITY );
root = null;
numElements = 0;
rowNumber = 0;
}
// <editor-fold defaultstate="collapsed" desc="Original Code">
/**
* Construct the binary heap.
* @param capacity the capacity of the binary heap.
*/
/**
public BinaryHeapwBinaryTree( int capacity )
{
currentSize = 0;
array = (AnyType[]) new Comparable[ capacity + 1 ];
}
/**
* Construct the binary heap given an array of items.
*/
/**
public BinaryHeapwBinaryTree( AnyType [ ] items )
{
currentSize = items.length;
array = (AnyType[]) new Comparable[ ( currentSize + 2 ) * 11 / 10 ];
int i = 1;
for( AnyType item : items )
array[ i++ ] = item;
buildHeap( );
}*/
/**
* Insert into the priority queue, maintaining heap order.
* Duplicates are allowed.
* @param x the item to insert.
*/
/**
public void insert( AnyType x )
{
numElements++;
if( currentSize == array.length - 1 )
enlargeArray( array.length * 2 + 1 );
// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;
}*/
// </editor-fold>
public void insert( AnyType x )
{
numElements++;
root = insert( x, root );
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
// <editor-fold defaultstate="collapsed" desc="Original Code">
/**
if( currentSize == array.length - 1 )
enlargeArray( array.length * 2 + 1 );
// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array hole ] = x;
*/// </editor-fold>
if( t == null ){
rowNumber++;
return new BinaryNode<AnyType>( x, null, null, null, null, null );
}
int compareResult = x.compareTo( t.element );
BinaryNode<AnyType> leftMost = findLeftMost(root);
if (Math.pow( 2,this.height(t)+1)== numElements){
rowNumber++;
leftMost.left = new BinaryNode<AnyType>
(x,leftMost,null ,null,null,null);
leftMost=leftMost.left;
}
return t;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the subtree.
*/
private void printTree( BinaryNode<AnyType> t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
public int getNumElements (){
return numElements;
}
public int getRowNumber (){
return rowNumber;
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findLeftMost( BinaryNode<AnyType> t )
{
if( t != null )
while( t.left != null )
t = t.left;
return t;
}
public int height (){
return height(root);
}
/**
* Internal method to compute height of a subtree.
* @param t the node that roots the subtree.
*/
private int height( BinaryNode<AnyType> t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ),
height( t.right ) );
}
// <editor-fold defaultstate="collapsed" desc="Original Code">
/**
private void enlargeArray( int newSize )
{
AnyType [ old = array;
array = (AnyType []) new Comparable[ newSize ];
for( int i = 0; i < old.length; i++ )
array[ i ] = old[ i ];
}*/
// </editor-fold>
/**
* Find the smallest item in the priority queue.
* @return the smallest item, or throw an UnderflowException if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return array[ 1 ];
}
/**
* Remove the smallest item from the priority queue.
* @return the smallest item, or throw an UnderflowException if empty.
*/
public AnyType deleteMin( )
{
if( isEmpty( ) )
throw new UnderflowException( );
AnyType minItem = findMin( );
array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );
return minItem;
}
/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
private void buildHeap( )
{
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}
/**
* Test if the priority queue is logically empty.
* @return true if empty, false otherwise.
*//**
public boolean isEmpty( )
{
return currentSize == 0;
}*/
/**
* Make the priority queue logically empty.
*/
public void makeEmpty( )
{
currentSize = 0;
}
private static final int DEFAULT_CAPACITY = 10;
private int currentSize; // Number of elements in heap
private AnyType [ ] array; // The heap array
/**
* Internal method to percolate down in the heap.
* @param hole the index at which the percolate begins.
*/
private void percolateDown( int hole )
{
int child;
AnyType tmp = array[ hole ];
for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize &&
array[ child + 1 ].compareTo( array[ child ] ) < 0 )
child++;
if( array[ child ].compareTo( tmp ) < 0 )
array[ hole ] = array[ child ];
else
break;
}
array[ hole ] = tmp;
}
// <editor-fold defaultstate="collapsed" desc="Original Code">
// Basic node stored in unbalanced binary search trees
private static class BinaryNode<AnyType>
{
// Constructors
BinaryNode( AnyType theElement )
{
this( theElement, null, null, null, null, null );
}
BinaryNode( AnyType theElement, BinaryNode<AnyType> pt,
BinaryNode<AnyType> lt, BinaryNode<AnyType> rt,
BinaryNode<AnyType> ls, BinaryNode<AnyType> rs )
{
element = theElement;
parent = pt;
left = lt;
right = rt;
leftSibling =ls;
rightSibling = rs;
nodeNumber +=nodeNumber;
}
AnyType element; // The data in the node
BinaryNode<AnyType> parent;
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
BinaryNode<AnyType> leftSibling; // left Sibling
BinaryNode<AnyType> rightSibling; // right Sibling
}// </editor-fold>
// Test program
public static void main( String [ ] args )
{
BinaryHeapwBinaryTree<Integer> h = new BinaryHeapwBinaryTree<Integer>( );
h.insert(1);
h.insert(2);
h.insert(3);
h.insert(4);
h.insert(5);
h.insert(6);
h.insert(7);
h.insert(8);
h.insert(9);
h.insert(10);
h.insert(11);
h.insert(12);
h.insert(13);
h.insert(14);
h.insert(15);
h.insert(16);
h.printTree();
System.out.println("\n\nelement #:" + h.getNumElements());
System.out.println("row #: " + h.getRowNumber());
/**
int numItems = 10000;
BinaryHeap<Integer> h = new BinaryHeap<Integer>( );
int i = 37;
for( i = 37; i != 0; i = ( i + 37 ) % numItems )
h.insert( i );
for( i = 1; i < numItems; i++ )
if( h.deleteMin( ) != i )
System.out.println( "Oops! " + i );
* */
}
}
Edited by: CjSaMmAeJS on Oct 28, 2008 8:13 AM
Edited by: CjSaMmAeJS on Oct 28, 2008 6:24 PM