Heap 堆积

Heap 堆积
Categories:
Tags:

Min Heap 最小堆积

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

Heap 堆积

Max Heap 最小堆积

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

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

Heap 堆积

时间複杂度 Time Complexity

操作 Time Complexity 时间複杂度
Lookup O(n)
Insert O(log N)
Delete O(log N)

Heap 结构

  • 由上到下
  • 由左到右

阵列索引顺序

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

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
阵列 10 6 7 5 15 17 12
索引位置 0 1 2 3 4 5 6

阵列数字演算法

节点 演算法
parent 母节点 (currentNumberIndex -1) / 2
left child 左节点 2 * currentNumberIndex + 1
right child 右节点 2 * currentNumberIndex + 2

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

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
  • 6 的索引位置：1
节点 演算法 母节点索引位置 母节点索引位置数字
parent 母节点 (1 - 1) / 2 0 10
left child 左节点 2 * 1 + 1 3 5
right child 右节点 2 * 1 + 2 4 15

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

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
  • 7 的索引位置：2
节点 演算法 母节点索引位置 母节点索引位置数字
parent 母节点 (2 - 1) / 2 0 10
left child 左节点 2 * 2 + 1 5 17
right child 右节点 2 * 2 + 2 6 12

Max Heap 比较流程

1. 从中间点找最大值

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

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

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
  • 索引 3 数字 5
节点 演算法 母节点索引位置 母节点索引位置数字
left child 左节点 2 * 3 + 1 7 找不到
right child 右节点 2 * 3 + 2 8 找不到

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

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

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

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

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
节点 演算法 母节点索引位置 母节点索引位置数字
left child 左节点 2 * 2 + 1 5 17
right child 右节点 2 * 2 + 2 6 12

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

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

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

阵列 10 6 17 5 15 7 12
索引位置 0 1 2 3 4 5 6

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

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

      10
    /    \
   6      17
 /  \    /  \
5   15  7   12
节点 演算法 母节点索引位置 母节点索引位置数字
left child 左节点 2 * 1 + 1 3 5
right child 右节点 2 * 1 + 2 4 15

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

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

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

阵列 10 15 17 5 6 7 12
索引位置 0 1 2 3 4 5 6

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

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

      10
    /    \
  15      17
 /  \    /  \
5    6  7   12
节点 演算法 母节点索引位置 母节点索引位置数字
left child 左节点 2 * 0 + 1 1 15
right child 右节点 2 * 0 + 2 2 17

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

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

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

阵列 17 15 10 5 6 7 12
索引位置 0 1 2 3 4 5 6

5. 比较最后交换的数字

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

      17
    /    \
  15      10
 /  \    /  \
5    6  7   12
节点 演算法 母节点索引位置 母节点索引位置数字
left child 左节点 2 * 2 + 1 5 5
right child 右节点 2 * 2 + 2 6 12

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

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

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

阵列 17 15 12 5 6 7 10
索引位置 0 1 2 3 4 5 6

参考资料