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

2 public class HeapPriorityQueue extends AbstractPriorityQueue {

3 / primary collection of priority queue entries /

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

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

6 public HeapPriorityQueue() { super(); }

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

8 public HeapPriorityQueue(Comparator comp) {

super(comp); }

9 // protected utilities

10 protected int parent(int j) { return (j1) / 2; } // truncating division

11 protected int left(int j) { return 2j + 1; }

12 protected int right(int j) { return 2j + 2; }

13 protected boolean hasLeft(int j) { return left(j) < heap.size(); }

14 protected boolean hasRight(int j) { return right(j) < heap.size(); }

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

16 protected void swap(int i, int j) {

17 Entry temp = heap.get(i);

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

19 heap.set(j, temp);

20 }

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

22 protected void upheap(int j) {

23 while (j > 0) { // continue until reaching root (or break statement)

24 int p = parent(j); 25 if (compare(heap.get(j), heap.get(p)) >= 0) break; // heap property veried

26 swap(j, p);

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

28 }

29 }

Use the HeapPriorityQueue class on the above lines of codes. Reimplement the downheap and upheap methods, such that these methods use recursion(and no loop). Save the code in file heapPriorityQueue.java. The file should contain the 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).