1 / An implementation of a priority queue using an array-based heap. / 2 public
ID: 3844509 • Letter: 1
Question
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).
Explanation / Answer
/ An implementation of a priority queue using an array-based heap. /
public class HeapPriorityQueue extends AbstractPriorityQueue {
protected ArrayList> heap = new ArrayList<>();
public HeapPriorityQueue()
{
super();
}
public HeapPriorityQueue(Comparator comp)
{
super(comp);
}
protected int parent(int j) {
return (j1) / 2;
}
protected int left(int j)
{
return 2j + 1;
}
protected int right(int j)
{
return 2j + 2;
}
protected boolean hasLeft(int j)
{
return left(j) < heap.size();
}
protected boolean hasRight(int j)
{
return right(j) < heap.size();
}
protected void swap(int i, int j) {
Entry temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
protected void upheap(int j) {
while (j > 0) {
int p = parent(j);
if (compare(heap.get(j), heap.get(p)) >= 0) break;
swap(j, p);
j = p;
}
}
-----Main Method------
public static vid man(String[] args)
{
// grow heap if needed
if (size >= heap.size() - 1) {
heap = this.resize();
}
// place element into heap at bottom
size++;
int index = size;
heap.add(value);
int index = this.size;
while (hasParent(index)
&& (parent(index).compareTo(heap.get(index)) > 0)) {
swap(index, parentIndex(index));
index = parentIndex(index);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.