Reimplement the downheap and upheap methods, such that these methods use recursion from the program provided below.

(and no loop). Write a main method that will create a heap using a sequence of insert operations: (5,A),

(4,B),(7,F),(1,D),(3,J),(6,L),(8,G),(2,H).

Please do not post an answer if cannot do this and the code must compile.

public class HeapPriorityQueue

{

/** An implementation of a priority queue using an array-based heap. */

public class HeapPriorityQueue extends AbstractPriorityQueue

{

/** primary collection of priority queue entries */

}

protected ArrayList> heap = new ArrayList<>( );

/** Creates an empty priority queue based on the natural ordering of its keys. */

public HeapPriorityQueue( )

{

super( );

}

/** Creates an empty priority queue using the given comparator to order keys. */

public HeapPriorityQueue(Comparator comp)

{

super(comp);

}

// protected utilities

protected int parent(int j)

{

return (j1) / 2;

} // truncating division

protected int left(int j)

{

return 2*j + 1;

}

protected int right(int j)

{

return 2*j + 2;

}

protected boolean hasLeft(int j)

{

return left(j) < heap.size( );

}

protected boolean hasRight(int j)

{

return right(j) < heap.size( );

}

/** Exchanges the entries at indices i and j of the array list. */

protected void swap(int i, int j)

{

Entry temp = heap.get(i);

heap.set(i, heap.get(j));

heap.set(j, temp);

}

/** Moves the entry at index j higher, if necessary, to restore the heap property. */

protected void upheap(int j)

{

while (j > 0)

{ // continue until reaching root (or break statement)

int p = parent(j);

if (compare(heap.get(j), heap.get(p)) >= 0) break; // heap property verified

swap(j, p);

j = p; // continue from the parent's location

}

}

/** Moves the entry at index j lower, if necessary, to restore the heap property. */

protected void downheap(int j)

{

while (hasLeft(j))

{ // continue to bottom (or break statement)

int leftIndex = left(j);

int smallChildIndex = leftIndex; // although right may be smaller

if (hasRight(j))

{

int rightIndex = right(j);

if (compare(heap.get(leftIndex), heap.get(rightIndex)) > 0)

smallChildIndex = rightIndex; // right child is smaller

}

if (compare(heap.get(smallChildIndex), heap.get(j)) >= 0)

break; // heap property has been restored

swap(j, smallChildIndex);

j = smallChildIndex; // continue at position of the child

}

}

// public methods

/** Returns the number of items in the priority queue. */

public int size( )

{

return heap.size( );

}

/** Returns (but does not remove) an entry with minimal key (if any). */

public Entry min( )

{

if (heap.isEmpty( )) return null;

return heap.get(0);

}

/** Inserts a key-value pair and returns the entry created. */

public Entry insert(K key, V value) throws IllegalArgumentException

{

checkKey(key); // auxiliary key-checking method (could throw exception)

Entry newest = new PQEntry<>(key, value);

heap.add(newest); // add to the end of the list

upheap(heap.size( ) 1); // upheap newly added entry

return newest;

}

/** Removes and returns an entry with minimal key (if any). */

public Entry removeMin( )

{

if (heap.isEmpty( )) return null;

Entry answer = heap.get(0);

swap(0, heap.size( ) 1); // put minimum item at the end

heap.remove(heap.size( ) 1); // and remove it from the list;

downheap(0); // then fix new root

return answer;

}

}