Write a method named replace that could be added to the HeapPriorityQueue class.
ID: 3711071 • Letter: W
Question
Write a method named replace that could be added to the HeapPriorityQueue class. This method accepts an element value value1and a replacement value value2, and finds and replaces one occurrence of value1 with value2 if value1 is present in the heap. You must maintain the heap's ordering after your method's work is done. For example, if a heap priority queue pq contains [/, 12, 41, 35, 56, 71, 52, 40, 84, 60, 78, 99, 66] in its internal heap array, the call of pq.replace(56, 30); would change pq's array to store [/, 12, 30, 35, 41, 71, 40, 52, 84, 60, 78, 99, 66]. A subsequent call of pq.replace(35, 88);would change pq to store [12, 30, 40, 41, 71, 52, 88, 84, 60, 78, 99, 66]. If the value1 is not found in the heap, no change occurs to the heap. You may assume that neither of the values passed is null.
You are allowed to call methods on your priority queue. This method should run in O(N) time where N is the number of elements in your queue. Assume that you are adding to the following class:
Explanation / Answer
Below is your method
public void replace(E value1, E value2) {
for (int i = 1; i <= size; i++) {
if (elements[i].equals(value1)) {
elements[i] = value2;
if (hasParent(i) && elements[i].compareTo(elements[parent(i)]) < 0) {
bubbleUp(i);
} else {
bubbleDown(i);
}
return;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.