堆排序

function heapSort(arr) {
    let n = arr.length;
    if (n <= 1) {
        return arr;
    }
    // build a heap 从后往前 从上到下
    for (let i = Math.floor(n/2); i >= 0; i--) {
        heapify(arr, i, n);
    }
    // sort
    // 循环来缩短堆的长度
    for (let i = 0; i < n; i++) {
        // 第一个和最后一个交换
        swap(arr, 0, n - 1 - i);
        // 只需heapify第一个元素 堆长度减一
        heapify(arr, 0, n - 2 - i);
    }
    return arr;
}

function swap(arr, a, b) {
    [arr[a], arr[b]] = [arr[b], arr[a]];
}
// ！！这里的size不是堆的长度，而是堆最后一个元素的索引 所以l<<size
function heapify(arr, i, size) {
    let l = 2*i+1;
    let r = 2*i+2;
    let largest = i;
    if (l <= size && arr[l] > arr[i]) {
        largest = l;
    }
    if (r <= size && arr[r] > arr[i]) {
        largest = r;
    }
    if (largest !== i) {
        swap(arr, i, largest);
        heapify(arr, largest, size);
    }
}

let arr = [4,5,3,4,5]
heapSort(arr)

第二版

function heapSort(arr) {
    let n = arr.length
    if (n <= 1) return arr
    // 从后往前 build heap
    for(let i = Math.floor(n/2); i >= 0; i--) {
        maxHeapify(arr, i, n)
    }
    for (let i = 0; i < n; i++) {
        swap(arr, 0, n - 1 - i)
        maxHeapify(arr, 0, n - 1 - i)
    }
    return arr
}

function swap(arr, a, b) {
    [arr[a],arr[b]] = [arr[b],arr[a]]
}
// size為堆的自然長度 所以l<size为条件
function maxHeapify(arr, i, size) {
    let l = 2 * i + 1, r = 2 * i + 2
    // 假定largest是i,但這是不穩定的
    let largest = i
    if(l<size && arr[l]>arr[largest]){
        largest = l
    }
    if(r<size && arr[r]>arr[largest]){
        largest = r
    }
    if(largest !== i){
        swap(arr, i, largest)
        // 交換後largest又不穩定了
        maxHeapify(arr, largest, size)
    }


}
let a = [5, 2, 4, 6, 1, 3]
heapSort(a); 

第三版 第二版的构造开始的位置存在问题

function heapSort(arr) {
    let n = arr.length
    if (n <= 1) return arr
    // 从后往前 build heap n为数组长度 n-1为最后节点索引 (n-1-1)/2为最后元素的父元素索引
    for(let i = Math.floor(n-2/2); i >= 0; i--) {
        maxHeapify(arr, i, n)
    }
    for (let i = 0; i < n; i++) {
        swap(arr, 0, n - 1 - i)
        maxHeapify(arr, 0, n - 1 - i)
    }
    return arr
}

function swap(arr, a, b) {
    [arr[a],arr[b]] = [arr[b],arr[a]]
}
// size為堆的自然長度
function maxHeapify(arr, i, size) {
    let l = 2 * i + 1, r = 2 * i + 2
    let largest = i
    if(l<size && arr[l]>arr[largest]){
        largest = l
    }
    if(r<size && arr[r]>arr[largest]){
        largest = r
    }
    if(largest !== i){
        swap(arr, i, largest)
        maxHeapify(arr, largest, size)
    }


}
let a = [5, 2, 4, 6, 1, 3]
heapSort(a); 

第四版 对第三版的交换和堆化的索引进行简化

function heapSort(arr) {
    let n = arr.length
    if (n <= 1) return arr
    // 从后往前 build heap n为数组长度 n-1为最后节点索引 (n-1-1)/2为最后元素的父元素索引
    for(let i = Math.floor(n-2/2); i >= 0; i--) {
        maxHeapify(arr, i, n)
    }
    // n-1为最后节点的索引
    for (let i = n - 1; i >= 0; i--) {
        // 这里i为索引
        swap(arr, 0, i)
        // 这里i为size,所以堆的最后节点的索引为i-1
        // i+1-1 = i i通过加一变成size，然后减一变成需要的size
        maxHeapify(arr, 0, i)
    }
    return arr
}

function swap(arr, a, b) {
    [arr[a],arr[b]] = [arr[b],arr[a]]
}
// size為堆的自然長度
function maxHeapify(arr, i, size) {
    let l = 2 * i + 1, r = 2 * i + 2
    let largest = i
    if(l<size && arr[l]>arr[largest]){
        largest = l
    }
    if(r<size && arr[r]>arr[largest]){
        largest = r
    }
    if(largest !== i){
        swap(arr, i, largest)
        maxHeapify(arr, largest, size)
    }


}
let a = [5, 2, 4, 6, 1, 3]
heapSort(a); 

ref

https://godbasin.github.io/2017/07/23/heap-sort/

https://www.bilibili.com/video/BV1Eb41147dK