Homework SoursePlease Provide Code in Either JAVA or C and provide CLEAR Ex
Please Provide Code in Either JAVA or C++ and provide CLEAR! Explanatin on what you are doing in the code. For goodfeedbackand full points. 10
Problem A binary heap is a binary tree based data structure that is often used to implement priority queues. Binary heaps, in turn, can be easily implemented using an array if the underlying tree is a complete binary tree. The tree nodes have a natural ordering: row by row starting at the root and moving left to right within each row If there are n nodes, this ordering specifies their positions 1, 2, within the array. Moving up and down the tree is easily simulated on the amay, using the fact that node number j has parent j/21 and children 2j and 2j+ 1. The goal of this problem is to build a heap from the given array. For this, go from the end to the beginning of a given array and let each element \"bubble up\" Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006. Given: A positive integer n 105 and array All..nl of integers from -10 to 105 Return: A permuted array A satisfying the binary max heap property: for any 2 Sisn, Alli/2 Alil. Sample Dataset 1 3 5 7 2 Sample output 7 5 1 3 2Solution
public class BinaryHeap implements PriorityQueue {
public BinaryHeap( ) {
currentSize = 0;
array = new Comparable[ DEFAULT_CAPACITY + 1 ];
}
public BinaryHeap( Comparable [ ] items ) {
currentSize = items.length;
array = new Comparable[ items.length + 1 ];
for( int i = 0; i < items.length; i++ )
array[ i + 1 ] = items[ i ];
buildHeap( );
}
public PriorityQueue.Position insert( Comparable x ) {
if( currentSize + 1 == array.length )
doubleArray( );
// Percolate up
int hole = ++currentSize;
array[ 0 ] = x;
for( ; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;
return null;
}
public void decreaseKey( PriorityQueue.Position p, Comparable newVal ) {
throw new UnsupportedOperationException( \"Cannot use decreaseKey for binary heap\" );
}
public Comparable findMin( ) {
if( isEmpty( ) )
throw new UnderflowException( \"Empty binary heap\" );
return array[ 1 ];
}
public Comparable deleteMin( ) {
Comparable minItem = findMin( );
array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );
return minItem;
}
private void buildHeap( ) {
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}
public boolean isEmpty( ) {
return currentSize == 0;
}
public int size( ) {
return currentSize;
}
public void makeEmpty( ) {
currentSize = 0;
}
private static final int DEFAULT_CAPACITY = 100;
private int currentSize; // Number of elements in heap
private Comparable [ ] array; // The heap array
private void percolateDown( int hole ) {
int child;
Comparable 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;
}
private void doubleArray( ) {
Comparable [ ] newArray;
newArray = new Comparable[ array.length * 2 ];
for( int i = 0; i < array.length; i++ )
newArray[ i ] = array[ i ];
array = newArray;
}
public static void main( String [ ] args ) {
int numItems = 10000;
BinaryHeap h1 = new BinaryHeap( );
Integer [ ] items = new Integer[ numItems - 1 ];
int i = 37;
int j;
for( i = 37, j = 0; i != 0; i = ( i + 37 ) % numItems, j++ ) {
h1.insert( new Integer( i ) );
items[ j ] = new Integer( i );
}
for( i = 1; i < numItems; i++ )
if( ((Integer)( h1.deleteMin( ) )).intValue( ) != i )
System.out.println( \"Oops! \" + i );
BinaryHeap h2 = new BinaryHeap( items );
for( i = 1; i < numItems; i++ )
if( ((Integer)( h2.deleteMin( ) )).intValue( ) != i )
System.out.println( \"Oops! \" + i );
}
}
public interface PriorityQueue {
public interface Position {
Comparable getValue( );
}
Position insert( Comparable x );
Comparable findMin( );
Comparable deleteMin( );
boolean isEmpty( );
void makeEmpty( );
int size( );
void decreaseKey( Position p, Comparable newVal );
}
public class UnderflowException extends RuntimeException {
public UnderflowException( String message ) {
super( message );
}
}
