MaxHeap Class

/*
 * Complete the 'heapsort' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */

function heapsort(arr) {

    //initialize the heap length to the size of the array
    let heapSize = arr.length;

    //create a max heap from the array (heapify)
    //for every element starting from the right side of the array
    for(let i = Math.floor((arr.length- 2)/2); i >=0; i--) {
        //bubble down that element
        bubbleDown(i);
    }

    //create bubble down function to help heapify and maintain heap
    function bubbleDown(parent) {
        //use get child function to get the larger child
        let child = getChild(parent);
        //while child is in heap and larger than the parent
        while(child <= heapSize - 1 && arr[child] > arr[parent]) {
            //swap
            [arr[child], arr[parent]] = [arr[parent], arr[child]]
            //get new child from new position and update parent position
            parent = child;
            child = getChild(child);
        }
    }

    //create a remove function to remove an element from the heap
    function removeFromHeap() {
        //swap the element at position 0 with the elemnt at the end of the heap
        [arr[0], arr[heapSize - 1]] = [arr[heapSize -1], arr[0]];
        //reduce heap size by 1
        heapSize--;
        //bubble down the new root (index 0)
        bubbleDown(0);
    }

    //create a helper to get the child for swapping with bubble down
    function getChild(parent) {
        //let left child = parent value * 2 + 1
        let leftChild = parent*2 + 1;
        //if left child the last element of the heap or is greater than the element one greater than it
        if(leftChild >= heapSize - 1 || arr[leftChild] >= arr[leftChild + 1]) {
            //return left
            return leftChild;
        } else {
        //else
            //return left + 1
            return leftChild + 1;
        }
    }

    //remove elements from the heap to sort
    //while heap size is > 1
    while(heapSize > 1) {
        //remove from heap
        removeFromHeap();
    }

    //return the array
    return arr;

}