Heap Sort an Array In Place

Complete HeapSort so heapSort(int[] a) sorts the array from smallest to largest IN PLACE, using the array itself as a max heap. You write three methods: siftDown, buildMaxHeap and heapSort.

Reminder: what a max heap is, and why it can sort. A max heap is a complete binary tree stored in an array where every parent is greater than or equal to its children, so the largest value sits at index 0. For index i the children are at 2 * i + 1 and 2 * i + 2. A heap is not sorted, it only knows where its largest value is, but that is enough: take the largest out, repair the heap, and the next largest is on top.

Heap sort runs in two phases inside the same array:

phase 1, build:   [4, 10, 3, 5, 1]  ->  [10, 5, 3, 4, 1]   a max heap
phase 2, repeat:  swap the root with the last unsorted slot,
                  shrink the heap by one, sift the new root down
                  [1, 5, 3, 4 | 10]  ->  [5, 4, 3, 1 | 10]  ->  ...

Every swap parks the current largest value just after the heap, so the sorted part grows from the back of the array while the heap shrinks from the front. It needs no second array and takes O(n log n) time on every input.

Requirements: 1. siftDown(int[] a, int size, int i) treats only the first size items of a as the heap. While the item at i has a child inside size, compare it with its larger child; if that child is larger, swap them and continue from the child, otherwise stop. 2. buildMaxHeap(int[] a) turns the whole array into a max heap by sifting down every parent, from index a.length / 2 - 1 back to 0. 3. heapSort(int[] a) calls buildMaxHeap, then for end from the last index down to 1: swap index 0 with index end, and sift index 0 down inside a heap of size end. 4. Empty and one-item arrays must work. Use the swap helper and do not create another array.

Do NOT write a main method.