Question

Write a second constructor that could be added to the HeapPriorityQueue class. This constructor accepts an array of elements as a parameter and uses that array as the heap rather than creating a new array. Of course, the array passed in is probably not in proper heap ordering, so you must rearrange it until it is. There's a neat trick for achieving this: If you just "bubble down" all of the non-leaf nodes of the heap, starting from the last non-leaf node and ending at the root, when you are done the array will be rearranged into proper heap order. (Why does this work?) For example, if you are passed the array [/, 46, 21, 15, 37, 51, 9, 12, 78, 31, 40, 8, 24], your constructor would rearrange it to be [/, 8, 21, 9, 31, 40, 15, 12, 78, 37, 46, 51, 24]. Assume that element 0 of the array is empty or null and can be ignored. You are allowed to call methods on your priority queue. This constructor should run in O(N) time where N is the number of elements in the array. (If you follow the algorithm described, though it seems like the runtime will be O(N log N), it turns out to be O(N) because the sum of the swap heights of the internal heap tree nodes is proportional to N.) Assume that you are adding to the following class: public class HeapPriorityQueue> { 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) {...} }

Answer 1

public HeapPriorityQueue(E arr[]) {
        elements = arr;
        size = arr.length - 1;
        
        for(int i=size/2; i>0; i--) {
                bubbleDown(i);
        }
}

Explanation: The code first assigns the given array to elements array. Then the non-leaf nodes are found in the first half of the array, because heap is a complete binary tree. So last half contains only leaves.
Hence we iterate on non-leaf nodes till root, and one by one, try to bubble them down.