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 you cannot do this and the code must compile and run. This is the second time I am posting this question because the last guy just copy pasted the code that I have given. The upheap and downheap methods must be RECURSIVE and there must be a main method that can execute the code with some hardcoded values.

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;

}

}

-----------------------------------------------------------------------

PriorityQueue Interface

public interface PriorityQueue

{

int size( );

boolean isEmpty( );

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

Entry min( );

Entry removeMin( );

}

---------------------------------------------------------------------------

AbstractPriorityQueue

public abstract class AbstractPriorityQueue implements PriorityQueue

{

protected static class PQEntry implements Entry

{

private K k; // key

private V v; // value

public PQEntry(K key, V value)

{

k = key;

v = value;

}

// methods of the Entry interface

public K getKey( )

{

return k;

}

public V getValue( )

{

return v;

}

// utilities not exposed as part of the Entry interface

protected void setKey(K key)

{

k = key;

}

public V setValue(V value)

{

return v = value;

}

} //----------- end of nested PQEntry class -----------

// instance variable for an AbstractPriorityQueue

/** The comparator defining the ordering of keys in the priority queue. */

private Comparator comp;

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

protected AbstractPriorityQueue(Comparator c)

{

comp = c;

}

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

protected AbstractPriorityQueue( )

{

this(new DefaultComparator( ));

}

/** Method for comparing two entries according to key */

protected int compare(Entry a, Entry b)

{

return comp.compare(a.getKey( ), b.getKey( ));

}

/** Determines whether a key is valid. */

protected boolean checkKey(K key) throws IllegalArgumentException

{

try

{

return (comp.compare(key,key) == 0); // see if key can be compared to itself

} catch (ClassCastException e)

{

throw new IllegalArgumentException("Incompatible key");

}

}

/** Tests whether the priority queue is empty. */

public boolean isEmpty( )

{

return size( ) == 0;

}

}

--------------------------------------------------------------------------------

Entry interface

public interface Entry

{

K getKey( ); // returns the key stored in this entry

V getValue( );

}

--------------------------------------------------------------------------------------------

DefaultComparator class

public class DefaultComparator implements Comparator

{

public int compare(E a, E b) throws ClassCastException

{

return ((Comparable) a).compareTo(b);

}

}