Heap Sort 堆积排序法

複杂度

Heap 结构

• 由上到下
• 由左到右

阵列索引顺序

阵列 [10, 6, 7, 5, 15, 17, 12] 会依序在 Heap 树 由上到下及由左到右放置

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12

阵列数字演算法

计算 [10, 6, 7, 5, 15, 17, 12] 阵列中数字 6 的节点

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12

• 6 的索引位置：1

计算 [10, 6, 7, 5, 15, 17, 12] 阵列中数字 7 的节点

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12

• 7 的索引位置：2

Max Heap 比较流程

1. 从中间点找最大值

比较左右节点，确认是否有彼此节点大的数字，如果有的话则将此节点交换往上移动

中间节点：Math.floor(整数长度 / 2) = 7/2 = 3.5 = 3

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12

• 索引 3 数字 5

确认中间节点的左右节点，都比中间节点 数字 5 较小

而因为找不到 数字 5 的左右节点，所以确认 数字 5 是这三个节点中最大

2. 往中间点左方移动，继续找最大值

索引 3 数字 5的左方是索引 2 数字 7

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12

这边会找到左右节点比母节点还大，将最大的子节点移动到母节点，那这整棵 Heap 树会变成

      10
    /    \
   6      17
 /  \    /  \
5   15  7   12

整个阵列会从 [10, 6, 7, 5, 15, 17, 12] 变成 [10, 6, 17, 5, 15, 7, 12]

3. 比较完成左方移动，继续找最大值

索引 2 数字 17的左方是索引 1 数字 6

      10
    /    \
   6      17
 /  \    /  \
5   15  7   12

这边会找到右节点比母节点还大，将最大的子节点移动到母节点，那这整棵 Heap 树会变成

      10
    /    \
  15      17
 /  \    /  \
5    6  7   12

整个阵列会从 [10, 6, 17, 5, 15, 7, 12] 变成 [10, 15, 17, 5, 6, 7, 12]

4. 比较完成左方移动，继续找最大值

索引 1 数字 15的左方是索引 0 数字 10

      10
    /    \
  15      17
 /  \    /  \
5    6  7   12

这边会找到右节点比母节点还大，将最大的子节点移动到母节点，那这整棵 Heap 树会变成

      17
    /    \
  15      10
 /  \    /  \
5    6  7   12

整个阵列会从 [10, 15, 17, 5, 6, 7, 12] 变成 [17, 15, 10, 5, 6, 7, 12]

5. 比较最后交换的数字

最后交换的数字是索引 2 数字 10

      17
    /    \
  15      10
 /  \    /  \
5    6  7   12

这边会找到右节点比母节点还大，将最大的子节点移动到母节点，那这整棵 Heap 树会变成

      17
    /    \
  15      12
 /  \    /  \
5    6  7   10

整个阵列会从 [17, 15, 10, 5, 6, 7, 12] 变成 [17, 15, 12, 5, 6, 7, 10]

最后就会完整的建立整个 Max Heap Tree，确定母节点的数字都是大于子节点

6. 从最后的节点开始排序 Heap 阵列

现在整个 Max Heap 阵列，可以确认的是第 1 个数字一定是整个阵列中最大的

所以为了排序需要将这个数字移动到阵列最后

      10
    /    \
  15      12
 /  \    /  
5    6  7   17

将阵列中最大数字 17 移动到最后之后，就不再检查最后的索引数字，所以将数字 17 移出整个 Max Heap Tree 的检查

但是将原本最后的索引数字 10 移动到第 1 个数字后，整个 Max Heap 阵列 的逻辑又被打破，为了维持状况，必须要母节点的数字都是大于子节点

所以可以从 索引 0 数字 10 开始，比较左右节点

这边会找到左节点比母节点还大，将最大的子节点移动到母节点，那这整棵 Heap 树会变成

      15
    /    \
  10      12
 /  \    /  
5    6  7   17

再来继续检查移动后的 索引 1 数字 10，确定是否有满足 Max Heap Tree

最后可以确认，左右节点都比 数字 10 还要小，这样就又产生出了一个新的 Max Heap Tree，母节点的数字都是大于子节点

7. 从最后的检查节点往左移动，继续排序 Heap 阵列

现在整个 Max Heap 阵列，可以确认的是第 1 个数字一定是整个阵列中最大的

所以为了排序需要将这个数字移动到阵列最后

      7
    /    \
  10      12
 /  \      
5    6  15   17

将阵列中最大数字 15 移动到最后之后，就不再检查最后的索引数字，所以将数字 15 移出整个 Max Heap Tree 的检查

但是将原本最后的索引数字 7 移动到第 1 个数字后，整个 Max Heap 阵列 的逻辑又被打破，为了维持状况，必须要母节点的数字都是大于子节点

所以可以从 索引 0 数字 7 开始，比较左右节点

这边会找到左右节点比母节点还大，将最大的子节点移动到母节点，那这整棵 Heap 树会变成

      12
    /    \
  10      7
 /  \      
5    6  15   17

再来继续检查移动后的 索引 2 数字 7，确定是否有满足 Max Heap Tree

而现在因为 索引 2 数字 7 没有其他的子节点了，所以这样就又产生出了一个新的 Max Heap Tree，母节点的数字都是大于子节点

8. 重複整个流程，从最后的检查节点往左移动，继续排序 Heap 阵列

整个 Tree 的比较流程会变成这样

最大 数字 12 与 数字 6 交换，数字 12 移出检查 Max Heap Tree

      6
    /    \
  10      7
 /        
5   12  15   17

数字 6 检查是否满足 Max Heap Tree，比较后调整 Max Heap Tree

      10
    /    \
  6       7
 /        
5   12  15   17

最大 数字 10 与 数字 5 交换，数字 10 移出检查 Max Heap Tree

      5
    /    \
  6       7

10  12  15   17

数字 5 检查是否满足 Max Heap Tree，比较后调整 Max Heap Tree

      7
    /    \
  6       5

10  12  15   17

最大 数字 7 与 数字 5 交换，数字 7 移出检查 Max Heap Tree

      5
    /    
  6       7

10  12  15   17

数字 5 检查是否满足 Max Heap Tree，比较后调整 Max Heap Tree

      6
    /    
  5       7

10  12  15   17

最大 数字 6 与 数字 5 交换，数字 6 移出检查 Max Heap Tree

      5

  6      7

10  12  15   17

这样整个移动到最后，就可以得到一个排序的阵列 [5, 6, 7, 10, 12, 15, 17]

演算法

1. 解析数字阵列转换成 Max Heap Tree

从整个阵列中的中间位置开始做 Max Heap Tree 检查 Math.floor(numberListLength / 2)

然后往阵列左侧扫描整个 Heap Tree

确保阵列第一个数字是整个 Max Heap Tree 最大的，并保持母节点的数字都是大于子节点

A. 比较自己级左右节点，把最大的节点移动到母节点

B. 当节点有做异动，继续对此节点做 Heap Tree

确认这个节点跟母节点的关係，也可以保持母节点的数字都是大于子节点

持续做到 Heap Tree 的第一个阵列数字

当结束后就可以确保第一个数字一定是整个 Heap Tree 最大的数字

2. 将数字由大到小依序交换至后方做排序

建立完 Max Heap Tree 后，第一个元素一定是最大的，将第一个元素最大数字与最后方的元素交换

这样整个阵列中的最后方往前方，会是由大到小排序

最后方元素确保是整个 Heap Tree 最大的数字后，将此元素移除整个 Heap Tree 不再检查

3. 重新建立最新的 Max Heap Tree 平衡树

原本最后方的元素因为被交换移动到第一个元素了，所以可能会破坏整个 Max Heap Tree 的原则，无法保持母节点的数字都是大于子节点

所以重新对剩馀的数字建立 Max Heap Tree，将剩馀数字最大的数字移动到后来 Max Heap Tree 的第一个元素

4. 持续对剩馀 Heap Tree 做 2~3 的步骤，直到比较到剩馀一个元素

元素会由大到小，持续地放在后方，持续的移除不在 Heap Tree 范围，直到整个 Max Heap Tree 剩 1 个元素

那最后整个阵列就会变成 由小到大 排序的阵列

程式

TypeScript

function heapify(numberList: number[], heapAvailableLength: number, currentNode: number):void {
    // 计算左节点位置
    const leftChildNode = currentNode * 2 + 1;
    // 计算右节点位置
    const rightChildNode = currentNode * 2 + 2;

    // 先预设最大的节点是自己
    let maxNode = currentNode;

    if (leftChildNode < heapAvailableLength && numberList[leftChildNode] > numberList[maxNode]) {
        // 如果「左节点」在 Heap 允许的范围内
        // 且「左节点数字」大于「目前最大节点数字」
        // 将左节点设定为目前最大节点
        maxNode = leftChildNode;
    }

    if (rightChildNode < heapAvailableLength && numberList[rightChildNode] > numberList[maxNode]) {
        // 如果「右节点」在 Heap 允许的范围内
        // 且「右节点数字」大于「目前最大节点数字」
        // 将右节点设定为目前最大节点
        maxNode = rightChildNode;
    }

    // 如果左右两边有任何一个比 node 大的话
    if (maxNode !== currentNode) {
        // 就把两个互换
        [numberList[currentNode], numberList[maxNode]] = [numberList[maxNode], numberList[currentNode]];

        // 接着继续对目前最大节点做 heapfiy
        heapify(numberList, heapAvailableLength, maxNode);
    }
}

function heapSort(numberList: number []): number[] {
    // 建立 max heap
    const numberListLength = numberList.length;
    // 起始 Heap 检查点
    let beginHeapCheckPointer = Math.floor(numberListLength / 2);
    // 建立 Heap Tree
    for (let i = beginHeapCheckPointer; i >= 0; i--) {
        heapify(numberList, numberListLength, i);
    }

    // 排序
    for (let i = numberListLength - 1; i > 0; i--) {
        // 从最后阵列元素位置开始，持续将第一个元素（最大元素）转移到最后方，让越大的数字放在后方
        [numberList[0], numberList[i]] = [numberList[i], numberList[0]];
        // 排除后方交换的元素，对第一个节点做剩馀数字的 Max Heap Tree
        heapify(numberList, i, 0);
    }

    return numberList;
}

let items = [10, 6, 7, 5, 15, 17, 12];

console.log(heapSort(items));

参考资料

• Investigating Heap Sort - Why Is Heap Sort Θ(n * log(n))? An Even Longer Really Long Answer. - YouTube
• 一起用 JavaScript 来複习经典排序法吧！