Practice-It

Write a method named replace that could be added to the HeapPriorityQueue class. This method accepts an element value value1 and 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:

public class HeapPriorityQueue<E extends Comparable<E>> {
    private E[] elements;
    private int size;

    public HeapPriorityQueue() {...}

    public void add(E value) {...}
    public boolean isEmpty() {...}
    public E peek() {...}
    public E remove() {...}
    public int size() {...}
    public String toString() {...}

    private void bubbleUp(int index) {...}
    private void bubbleDown(int index) {...}
    private int parent(int index) {...}
    private int leftChild(int index) {...}
    private int rightChild(int index) {...}
    private boolean hasParent(int index) {...}
    private boolean hasLeftChild(int index) {...}
    private boolean hasLeftRightChild(int index) {...}
    private void swap(E[] array, int index1, int index2) {...}
}