Build a Max Heap From an Unsorted Array

Complete the MaxHeap(int[] values) constructor and the private siftDown(int i) method, so a heap can be built from an unsorted array in one go instead of inserting the values one at a time.

Reminder: what a max heap is. A max heap is a complete binary tree stored in an array, filled left to right with no gaps, where every parent is greater than or equal to its children. That puts the largest value at index 0. Like every heap it is NOT a binary search tree: it only promises the parent-child rule. For the item at index i, the children are at 2 * i + 1 and 2 * i + 2.

start: [3, 9, 2, 1, 4, 5]      last parent = index 2

         3
       /   \
      9     2
     / \   /
    1   4 5

Building a heap from an array is called heapify. Every index from size / 2 to the end is a leaf, and a single leaf is already a valid heap, so only the parents need fixing. Start at the last parent, index size / 2 - 1, and walk backwards to index 0, sifting each one down. By the time you reach a node, both subtrees below it are already heaps, so sinking that one node into place is all it takes.

Requirements: 1. siftDown(int i) moves the item at index i down: while it has a left child (an index less than size), find the larger child; if that child is larger than the item, swap them and carry on from the child's index, otherwise stop. 2. When both children exist, always compare against the larger one. 3. The constructor already copies values into items and sets size. Finish it with a loop from size / 2 - 1 down to 0 that calls siftDown on each index. 4. Do not change the caller's values array, and do not change removeMax, which already relies on your siftDown.

Do NOT write a main method.