1 / An implementation of a priority queue using an array-based heap. / 2 public
ID: 3844330 • Letter: 1
Question
1 / An implementation of a priority queue using an array-based heap. /
2 public class HeapPriorityQueue<K,V> extends AbstractPriorityQueue<K,V> {
3 / primary collection of priority queue entries /
4 protected ArrayList<Entry<K,V>> 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<K> 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<K,V> 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).
Explanation / Answer
CODE:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.