The keys in a binary heap are according to the heap-order property. Suppose that
ID: 3545672 • Letter: T
Question
The keys in a binary heap are according to the heap-order property. Suppose that they are scrambled. Write a program FixHeap.java fixing the heap. Use the array representation of the heap. The keys should be provided in a string as the input (so that TA can run it as "java FixHeap string"). Implement 3 ways of fixing the heap and compute the number of swaps in each (3 numbers). 1) Fixing the heap. Repeat the following step: find the two nodes with indices i<j such that Heap[i] and Heap[j] are not in heap-order (read the definition of the heap-order in the notes. it involves a node and its parent!) and j is maximum, then swap them. Fix the heap and count the number of swaps. 2) Fix the heap by constructing it. Take the input sequence of numbers and insert them into an empty heap. Count the total number of swaps in all insertions. 3) Construction of the heap by merging. Use the algorithm with O(n) running time (using downheap to restore the heap-order property). Count the total number of swaps.
Sample Output:
Initial array: [9, 8, 7, 6, 5, 4, 3, 2, 1] Method one (Fixed): Number of swaps: 11 [1, 2, 4, 3, 8, 5, 9, 7, 6] Method two (Insertion): Number of swaps: 16 [1, 2, 4, 3, 7, 8, 5, 9, 6] Method three (Merge): Number of swaps: 7 [1, 2, 3, 6, 5, 4, 7, 8, 9]
Explanation / Answer
Dear sirs,
I hope that you find this answer to your liking:
public class BinaryHeap implements PriorityQueue {
//Construct the binary heap.
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;
}
// Test program
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 );
}
}
This was answered by:
EnginnerExtraordinair
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.