JavaScript - 排序算法 - 堆排序

特点：

• 时间复杂度：O(nlog2n)
• 堆排序是不稳定的排序算法

原理：

• 利用大顶堆排序（升序）
• 利用小顶堆排序（降序）
• 初始时将待排序数组生成堆结构
• 将堆顶换到堆尾，并取出放入结果集
• 重新维护堆结构，获取下一个堆顶，重复上述操作
• 当堆被清空，排序完成

代码实现：

• 堆排序的核心在于维护堆结构，并实现一个重置堆的方法（heapify）。
• 1. 使用数组存储堆结构（使用树结构同样可以，但是浪费空间）
     重要性质：节点关系与数组index的映射关系

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

// 数据结构-最大堆
let heap = [];

// utils，交换位置
function swap(index1, index2) {
    [heap[index1], heap[index2]] = [heap[index2], heap[index1]];
}

// 上浮shiftUp，维护堆的属性
function shiftUp(index) {
    let fatherIndex = Math.floor((index - 1) / 2);

    if (index !== 0 && heap[fatherIndex] < heap[index]) {
        swap(fatherIndex, index);
        shiftUp(fatherIndex);
    }
}

// 下沉shiftDown，也被称为堆化
function shiftDown(index) {
    // 判断是否比子节点小
    let leftChild = index * 2 + 1;
    let rightChild = index * 2 + 2;

    if (leftChild < heap.length && heap[index] < heap[leftChild]) {
        swap(index, leftChild);
        shiftDown(leftChild);
    }
    if (rightChild < heap.length && heap[index] < heap[rightChild]) {
        swap(index, rightChild);
        shiftDown(rightChild);
    }
}

function heapSort(arr) {
    // 建堆
    for (let i of arr) {
        heap.push(i);
        shiftUp(heap.length - 1);
    }
    let res = [];

    while (heap.length > 0) {
        swap(0, heap.length - 1);
        res.push(heap.pop());
        shiftDown(0);
    }
    return res;
}