The keys in a binary heap are according to the heap-order property. Suppose that
ID: 3545243 • 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 and j such that Heap[i] and Heap[j] are not in heap-order 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.
- PA2. Swaps computed by the first method. Thanks, Michael.
Input Tree Heap Ordered Output # of Swaps 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0 9 8 7 6 5 4 3 2 1 1 2 4 3 8 7 9 5 6 10 11 33 22 65 9 15 7 7 9 11 65 33 15 22 3
- Another code for reading the input numbers in PA2. Thanks, Ahmad!
public static void main(String[] args) { ArrayList tree = new ArrayList(); int size = args.length; // Check if args[] is empty if (size == 0) System.out.print("Input is empty!"); else { // For loop fills ArrayList with contents of args[] for (String arg : args) tree.add(Integer.parseInt(arg)); // Prints the ArrayList to verify contents printArrayList(tree); } } - Here is the code for the input in PA2. Thanks, Andrew!
public static void main(String[] args){ if (args.length == 0){ printHelp(); System.exit(0); } Integer [] treeArr = new Integer [args.length + 1]; treeArr [0] = args.length; for (int i = 0; i < args.length; i++){ treeArr [i+1] = Integer.parseInt(args [i]); } } - The input string in PA2 is the sequence of integer numbers with spaces between them. If anyone email me a code for reading it, I can post it here for everyone. The examples of input numbers:
1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 11 33 22 65 9 15 7
Explanation / Answer
public class BinaryHeap implements PriorityQueue {
/**
* Construct the binary heap.
*/
public BinaryHeap( ) {
currentSize = 0;
array = new Comparable[ DEFAULT_CAPACITY + 1 ];
}
/**
* Construct the binary heap from an array.
* @param items the inital items in the binary heap.
*/
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( );
}
/**
* Insert into the priority queue.
* Duplicates are allowed.
* @param x the item to insert.
* @return null, signifying that decreaseKey cannot be used.
*/
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;
}
/**
* @throws UnsupportedOperationException because no Positions are returned
* by the insert method for BinaryHeap.
*/
public void decreaseKey( PriorityQueue.Position p, Comparable newVal ) {
throw new UnsupportedOperationException( "Cannot use decreaseKey for binary heap" );
}
/**
* Find the smallest item in the priority queue.
* @return the smallest item.
* @throws UnderflowException if empty.
*/
public Comparable findMin( ) {
if( isEmpty( ) )
throw new UnderflowException( "Empty binary heap" );
return array[ 1 ];
}
/**
* Remove the smallest item from the priority queue.
* @return the smallest item.
* @throws UnderflowException if empty.
*/
public Comparable deleteMin( ) {
Comparable 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;
}
/**
* Returns size.
* @return current size.
*/
public int size( ) {
return currentSize;
}
/**
* Make the priority queue logically empty.
*/
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
/**
* Internal method to percolate down in the heap.
* @param hole the index at which the percolate begins.
*/
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;
}
/**
* Internal method to extend array.
*/
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 );
}
}
// PriorityQueue interface
//
// ******************PUBLIC OPERATIONS*********************
// Position 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
// int size( ) --> Return size
// void decreaseKey( p, v)--> Decrease value in p to v
// ******************ERRORS********************************
// Throws UnderflowException for findMin and deleteMin when empty
/**
* PriorityQueue interface.
* Some priority queues may support a decreaseKey operation,
* but this is considered an advanced operation. If so,
* a Position is returned by insert.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public interface PriorityQueue {
/**
* The Position interface represents a type that can
* be used for the decreaseKey operation.
*/
public interface Position {
/**
* Returns the value stored at this position.
* @return the value stored at this position.
*/
Comparable getValue( );
}
/**
* Insert into the priority queue, maintaining heap order.
* Duplicates are allowed.
* @param x the item to insert.
* @return may return a Position useful for decreaseKey.
*/
Position insert( Comparable x );
/**
* Find the smallest item in the priority queue.
* @return the smallest item.
* @throws UnderflowException if empty.
*/
Comparable findMin( );
/**
* Remove the smallest item from the priority queue.
* @return the smallest item.
* @throws UnderflowException if empty.
*/
Comparable deleteMin( );
/**
* Test if the priority queue is logically empty.
* @return true if empty, false otherwise.
*/
boolean isEmpty( );
/**
* Make the priority queue logically empty.
*/
void makeEmpty( );
/**
* Returns the size.
* @return current size.
*/
int size( );
/**
* Change the value of the item stored in the pairing heap.
* This is considered an advanced operation and might not
* be supported by all priority queues. A priority queue
* will signal its intention to not support decreaseKey by
* having insert return null consistently.
* @param p any non-null Position returned by insert.
* @param newVal the new value, which must be smaller
* than the currently stored value.
* @throws IllegalArgumentException if p invalid.
* @throws UnsupportedOperationException if appropriate.
*/
void decreaseKey( Position p, Comparable newVal );
}
/**
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
* @author Mark Allen Weiss
*/
public class UnderflowException extends RuntimeException {
/**
* Construct this exception object.
* @param message the error message.
*/
public UnderflowException( String message ) {
super( message );
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.