Image by macrovector on Freepik

时间複杂度 Time Complexity

Min Heap 最小堆积

完全二元树所有父节点都比子节点要小，就属于最小堆积

Max Heap 最小堆积

完全二元树所有父节点都比子节点要大，就属于最大堆积

• Binary Heap 和记忆体中的 Heap 没有关係
• Parent 的数值一定大于 Child
• Binary Heap 中 parent node 的数值，一定大于 child node 的数值。
• root 会是所有 Node 中的最大值。
• Binary Heap 很常被使用在 Priority Queue。

时间複杂度 Time Complexity

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]

参考资料

• Investigating Heap Sort - Why Is Heap Sort Θ(n * log(n))? An Even Longer Really Long Answer. - YouTube
• Implement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type) - YouTube
• [资料结构] 堆积 (Heap) - iT 邦帮忙::一起帮忙解决难题，拯救 IT 人的一天
• [资料结构] Binary Heap | PJCHENder 未整理笔记

Donate KJ 贊助作者喝咖啡

如果這篇文章對你有幫助的話，可以透過下面支付方式贊助作者喝咖啡，如果有什麼建議或想說的話可以贊助並留言給我

If this article has been helpful to you, you can support the author by treating them to a coffee through the payment options below. If you have any suggestions or comments, feel free to sponsor and leave a message for me!