PLEASE PLEASE PLEASE DO NOT ANSWER IF YOU DON'T KNOW THE MATERIAL. I AM POSTING THIS FOR THE THIRD TIME NOW SO PLEASE DON'T WASTE MY QUESTIONS. THIS HAS TO BE IMPLEMENTED IN JAVA

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);

}

}