Practice-It

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<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) {...}
}