SOURCE

let length // 声明一个全局变量标记每次构建最大堆需要操作的长度。（因为在排序过程中，随着已排序数组的增长，待排序数组长度会递减）

const swap = (array, i, j) => {
    const temp = array[i]
    array[i] = array[j]
    array[j] = temp
}

const heapify = (array, i) => {
    /* 
        根据最大（小）堆的定义可得，
        若父节点位置为i，则有：
        父节点i的左子节点在位置 (2*i+1);
        父节点i的右子节点在位置 (2*i+2);
    */
    let largest = i
    const left = i * 2 + 1
    const right = i * 2 + 2
    if (left < length && array[left] > array[largest]) {
        largest = left
    }
    if (right < length && array[right] > array[largest]) {
        largest = right
    }
    if (largest !== i) {
        swap(array, largest, i)
        // 继续向下比较，以满足最大堆的条件
        heapify(array, largest)
    }
}

const buildMaxHeap = array => {
    length = array.length
    // 从下往上，从右往左构建最大堆
    for (let i = Math.floor(length / 2); i >= 0; i--) {
        heapify(array, i)
    }
}

const heapSort = array => {
    // 构建最大堆
    buildMaxHeap(array)
    // 堆的收尾互换，直至堆尺寸为1
    for (let i = length - 1; i > 0; i--) {
        swap(array, i, 0)
        length--
        heapify(array, 0)
    }
    return array
}

console.log(heapSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]))