曹耘豪的博客

数据结构之堆

  1. 堆的特点
  2. 堆的示例
  3. 堆的底层实现
  4. 从某个节点开始向下调整堆（Heapify）
  5. 将一个随机数组调整为堆（Build Heap）

堆的特点

堆的示例

1
2
3
4
5
6
7
8
9
10
11
      1
    /   \
  7       3
 / \     / \
8   9   4   5
   
      1
    /   \
  7       3
 / \
8   9

堆的底层实现

由于堆是一个完全二叉树，所以使用数组实现会比较方便

对于以下最小堆，使用数组实现是[0, 1, 2, 3, 4, 5, 6]

1
2
3
4
5
      0
    /   \
  1       2
 / \     / \
3   4   5   6

对于任意一个子节点（pos = i）

从某个节点开始向下调整堆（Heapify）

1
2
3
4
5
6
7
8
9
def heapify(arr, i):
    left, right, target = i * 2 + 1, i * 2 + 2, i
    if left < len(arr) and arr[left] < arr[target]:
        target = left
    if right < len(arr) and arr[right] < arr[target]:
        target = right
    if target != i:
        arr[target], arr[i] = arr[i], arr[target]
        heapify(arr, target) # 递归调整

将一个随机数组调整为堆（Build Heap）

从最后一个父节点开始，向前对每个父节点执行heapify

1
2
3
4
def build_heap(arr):
    last_parent = (len(arr) - 1 - 1) // 2
    for parent in range(last_parent, -1, -1):
        heapify(arr, parent)
  算法