Assignment : Your task is to write an appropriate recursive implementation of "reheapDown" so that the dequeue method can do what it is supposed to do

import java.lang.reflect.Array;

// Models a maxheap

public class Heap> implements PriorityQueueInterface {

private static int DEFAULT_CAPACITY = 100; // Default maxnumber of elements

private int currentSize; // Number of elements in the heap

private T[] elements; // Heap array

@SuppressWarnings("unchecked")

public Heap(Class extends="" t=""?> clazz) {

// Default constructor, returns an empty heap with default capacity

elements =(T[])Array.newInstance(clazz, DEFAULT_CAPACITY);

currentSize = 0;

}

@SuppressWarnings("unchecked")

public Heap(Class extends="" t=""?> clazz,int maxSize) {

// Returns an empty heap with room for maxSize elements

elements = (T[])Array.newInstance(clazz,maxSize);

currentSize = 0;

}

public boolean isEmpty() {

// Returns true if this priority queue is empty; otherwise, returns false.

return (currentSize == 0);

}

public boolean isFull() {

// Returns true if this priority queue is full; otherwise, returns false.

return (currentSize == elements.length);

}

/***************************** ITERATIVE ENQUEUE **********************************/

private void reheapUp(T item) {

// Inserts element into the tree and maintains shape and order properties.

int hole = currentSize; // Add "hole" in next free position

int holeparent = (hole-1)/2; // A hole's parent is in index (hole-1)/2

// While hole is not the root & element > hole's parent

while (hole > 0 && (item.compareTo(elements[ holeparent ])) > 0) {

elements[hole] = elements[ holeparent ]; // Move hole's parent down

hole = holeparent; // and then move hole up

holeparent = (hole-1)/2; // as well as its parent

}

// The correct position has been found --> item is inserted into hole

// and currentSize is incremented

elements[hole] = item;

currentSize++;

}

public void enqueue(T element) throws PriorityQueueOverflowException {

// Throws PriorityQueueOverflowException if this priority queue is full;

// otherwise, adds element to this priority queue.

if (isFull()) {

throw new PriorityQueueOverflowException("Priority queue is full");

}

else {

reheapUp(element);

}

}

/***************************** RECURSIVE ENQUEUE **********************************/

private void reheapUpRec(int root, int last) {

// Recursive reheapUp, restores heap properties starting by reheaping up the element

// in index "last" (the right most leaf)

int parent;

if (last > root) { // tree is not empty

parent = (last-1)/2;

// if elements[bottom] > than its parent it should be moved up

if ((elements[parent].compareTo(elements[last]))

T temp = elements[parent];

elements[parent] = elements[last];

elements[last] = temp;

reheapUpRec(root, parent);

}

}

}

public void enqueueRec(T element) throws PriorityQueueOverflowException {

// Recursive enqueue. Throws PriorityQueueOverflowException if priority queue is full;

// otherwise, adds element to the priority queue.

if (isFull()) {

throw new PriorityQueueOverflowException("Priority queue is full");

}

else {

elements[currentSize] = element; // add new element

currentSize++; // increment size

reheapUpRec(0, currentSize-1); // restore heap properties

}

}

/****************************** RECURSIVE DEQUEUE ******************************/

private void reheapDown(int root, int last) {

// Restores heap properties starting by reheaping down the element in index "root".

// last indicates the position of the last element in the heap (right most leaf)

// No code given - part of RO 5 :)

/***** INSERT CODE HERE! *****/

}

public T dequeue() throws PriorityQueueUnderflowException {

// Throws PriorityQueueUnderflowException if the priority queue is empty;

// otherwise, removes element with highest priority from this

// priority queue and returns it.

T toReturn; // element to be dequeued and returned

//T toMove; // element to move down heap

if (isEmpty()) {

throw new PriorityQueueUnderflowException("Priority queue is empty");

}

else {

toReturn = elements[0]; // remember the root so that we can return it

elements[0] = elements[currentSize-1]; // copy the element in the last position (the one

// to reheap down) into the root position

currentSize--; // and remove the element form the heap

if (!isEmpty()) { // if the heap is not empty

reheapDown(0, currentSize-1); // restore heap properties

}

return toReturn; // return the original root, i.e. the largest element

}

}

/************* HELPER METHOD FOR PRINTING ELEMENTS IN HEAP ******************/

public String toString() {

// Returns a string of all the heap elements.

String theHeap = new String("the heap is: ");

String info;

for (int index = 0; index

info = elements[index].toString();

theHeap = theHeap + index + ". " + info + " ";

}

return theHeap;

}

}