Below is a class for max heap. Write a subclass (derived class) of MaxHeap which

Question

Below is a class for max heap. Write a subclass (derived class) of MaxHeap which implements a priority queue. Your class (public class PriorityQueue) should have the two nethods: public void insert(T t) // inserts new element into // priority queue public T remove() // removes and returns element from // priority queue; returns null if // the priority queue is empty public class MaxHeap { protected final int SIZE = 100; protected int[] store = new int[SIZE]; protected int length; // the number of elerents in store // which are heap elements // moves store[index down into heap order protected void pushDown(int index)// moves store[index down into heap order { /* some stuff is here */ } // moves store(index up into heap order protected void pushUp(int index) { /* some stuff is here */} }

Explanation / Answer

The following code shows how to implement a priority queue in Java: // BinaryHeap class // // CONSTRUCTION: empty or with initial array. // // ******************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 for findMin and deleteMin when empty /** * Implements a binary heap. * Note that all "matching" is based on the compareTo method. * @author Mark Allen Weiss */ 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 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 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

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.