堆（Heap）：高效的优先级队列实现

什么是堆？

堆是一种特殊的完全二叉树，满足以下性质：

• 堆序性：每个节点的值与其子节点满足特定关系
  • 最小堆：父节点 ≤ 子节点（根最小）
  • 最大堆：父节点 ≥ 子节点（根最大）
• 结构性：完全二叉树，除最后一层外完全填充，最后一层左对齐

最小堆：[1]/   \[3]     [2]/ \     /
[5][9] [4]最大堆：[9]/   \[5]     [8]/ \     /
[2][4] [3]

为什么需要堆结构？

1. 高效极值访问：O(1)时间获取最小/最大值
2. 动态优先级管理：实时处理优先级变化的数据
3. 空间效率：可用数组紧凑存储（无指针开销）
4. 算法优化：堆排序、Dijkstra算法等核心组件

堆的核心操作与复杂度

堆的数组表示

完全二叉树特性使得堆可以用数组高效存储：

• 父节点索引：parent(i) = (i-1)//2
• 左子节点索引：left(i) = 2*i + 1
• 右子节点索引：right(i) = 2*i + 2

示例：

最大堆:70/    \50     60/ \    / \30 20  10 40数组表示: [70, 50, 60, 30, 20, 10, 40]

基本操作实现

1、上浮（Heapify Up）

def heapify_up(heap, i):while i > 0:parent = (i - 1) // 2if heap[i] > heap[parent]:  # 最大堆示例heap[i], heap[parent] = heap[parent], heap[i]i = parentelse:break

（1）初始状态（插入新节点）

假设当前最大堆的数组为 [9, 5, 8, 3, 4, 2]，结构如下：

          [9]/   \[5]     [8]/ \     /[3][4] [2]

现在插入一个新节点 10 到堆的末尾，数组变为 [9, 5, 8, 3, 4, 2, 10]，破坏了堆性质：

          [9]/   \[5]     [8]/ \     / \[3][4]  [2] [10]   ← 节点10需要上浮

（2）执行 heapify_up(heap, i=6) 的分步图解

（i=6 是新节点 10 的索引）

第1次循环：

1. 找到父节点：

   • parent = (6-1)//2 = 2（节点8）
   • 比较 heap=10 和 heap=8：10 > 8 → 需要交换

2. 交换并更新：

   • 交换 heap 和 heap（10 ↔ 8）
   • 数组变为 [9, 5, 10, 3, 4, 2, 8]
   • i 更新为 parent = 2（继续检查节点10）

          [9]/   \[5]     [10]     ← 节点10上浮到这里/ \     / \[3][4] [2][8]      ← 原节点8下沉

第2次循环：

1. 找到新的父节点：

   • parent = (2-1)//2 = 0（节点9）
   • 比较 heap=10 和 heap=9：10 > 9 → 需要交换

2. 交换并更新：

   • 交换 heap 和 heap（10 ↔ 9）
   • 数组变为 [10, 5, 9, 3, 4, 2, 8]
   • i 更新为 parent = 0（到达根节点）

          [10]         ← 节点10成为新根/   \[5]     [9]      ← 节点9下沉/ \     / \[3][4]  [2] [8]

终止条件：

• 现在 i=0（根节点），循环终止。

（3）最终最大堆

数组为 [10, 5, 9, 3, 4, 2, 8]，结构如下：

          [10]         ← 根节点最大/   \[5]     [9]      ← 每个父节点 ≥ 子节点/ \     / \[3][4] [2][8]

（4）关键点总结：

1. heapify_up 的作用：从节点 i 开始，通过不断与父节点比较并交换，使其上浮到正确位置。
2. 触发场景：通常在插入新元素后调用（先追加到末尾，再上浮）。
3. 终止条件：当节点 i 到达根节点，或父节点已经更大时停止。
4. 时间复杂度：最坏情况从叶子上浮到根，为 O(log n)。

（5）对比 heapify_down 和 heapify_up：

2、下沉（Heapify Down）

def heapify_down(heap, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and heap[left] > heap[largest]:largest = leftif right < n and heap[right] > heap[largest]:largest = rightif largest != i:heap[i], heap[largest] = heap[largest], heap[i]i = largestelse:break

（1）初始最大堆（已破坏）

假设我们有一个部分破坏的堆（只有根节点不满足堆性质），数组表示为 [3, 9, 8, 5, 4, 2]，结构如下：

          [3]          ← 根节点值(3)比子节点(9,8)小，需要下沉/   \[9]     [8]/ \     /[5][4] [2]

（2）执行 heapify_down(heap, n=6, i=0) 的分步图解

第1次循环：

1. 比较根节点和子节点：

   • left = 2*0+1 = 1（值=9）
   • right = 2*0+2 = 2（值=8）
   • largest 初始为 0（值=3）
   • 比较发现 left(9) > largest(3) → largest = left = 1
   • right(8) > largest(9)？否，保持 largest=1

2. 交换并更新：

   • 交换 heap 和 heap（3 ↔ 9）
   • 数组变为 [9, 3, 8, 5, 4, 2]
   • i 更新为 largest = 1（继续检查节点3）

          [9]          ← 根节点已修复/   \[3]     [8]      ← 节点3需要继续下沉/ \     /[5][4] [2]

第2次循环：

1. 检查新的 i=1（值=3）：

   • left = 2*1+1 = 3（值=5）
   • right = 2*1+2 = 4（值=4）
   • largest 初始为 1（值=3）
   • left(5) > largest(3) → largest = left = 3
   • right(4) > largest(5)？否，保持 largest=3

2. 交换并更新：

   • 交换 heap 和 heap（3 ↔ 5）
   • 数组变为 [9, 5, 8, 3, 4, 2]
   • i 更新为 largest = 3（继续检查节点3）

          [9]/   \[5]     [8]      ← 节点5已满足堆性质/ \     /[3][4] [2]         ← 节点3是叶子节点，无需处理

终止条件：

• 现在 i=3 是叶子节点（无子节点），largest == i，循环终止。

（3）最终最大堆

数组为 [9, 5, 8, 3, 4, 2]，结构如下：

          [9]          ← 根节点最大/   \[5]     [8]      ← 每个父节点 ≥ 子节点/ \     /[3][4] [2]

（4）关键点总结：

1. heapify_down 的作用：从节点 i 开始，通过不断与更大的子节点交换，使其下沉到正确位置。
2. 终止条件：当节点 i 没有子节点，或已经比子节点大时停止。
3. 时间复杂度：最坏情况从根下沉到叶子，为 O(log n)。

3、插入元素

def heappush(heap, item):heap.append(item)heapify_up(heap, len(heap)-1)

heappush 用于向堆中插入一个新元素，并维护堆的性质。它分为两步：

1. heap.append(item)：将新元素添加到堆的末尾（保持完全二叉树的结构性）。
2. heapify_up(heap, len(heap)-1)：从新插入的节点开始，向上调整（heapify_up），直到满足堆序性。

分步图解

假设当前有一个 最大堆，初始数组为 [10, 5, 9, 3, 4, 2, 8]，结构如下：

          [10]/    \[5]      [9]/ \      / \[3][4]   [2] [8]

现在要插入一个新元素 7。

Step 1: heap.append(7)

将 7 添加到堆的末尾，数组变为 [10, 5, 9, 3, 4, 2, 8, 7]，结构如下：

          [10]/    \[5]      [9]/ \      / \[3][4]   [2] [8]/[7]       ← 新插入的节点7（索引=7）

此时，7 的父节点是 3（索引 (7-1)//2 = 3），由于 7 > 3，破坏了最大堆性质（父节点应 ≥ 子节点），需要调整。

Step 2: heapify_up(heap, i=7)

1. 第一次循环：
   • i = 7（节点7）
   • parent = (7-1)//2 = 3（节点3）
   • 比较 heap = 7 和 heap = 3，发现 7 > 3，需要交换。
   • 交换 7 和 3，数组变为 [10, 5, 9, 7, 4, 2, 8, 3]。
   • i 更新为 parent = 3（现在 7 位于索引3）。

          [10]/    \[5]      [9]/ \      / \[7][4]   [2] [8]/[3]

1. 第二次循环：
   • i = 3（节点7）
   • parent = (3-1)//2 = 1（节点5）
   • 比较 heap = 7 和 heap = 5，发现 7 > 5，需要交换。
   • 交换 7 和 5，数组变为 [10, 7, 9, 5, 4, 2, 8, 3]。
   • i 更新为 parent = 1（现在 7 位于索引1）。

          [10]/    \[7]      [9]/ \      / \[5][4]   [2] [8]/[3]

1. 第三次循环：
   • i = 1（节点7）
   • parent = (1-1)//2 = 0（节点10）
   • 比较 heap = 7 和 heap = 10，发现 7 ≤ 10，停止调整（堆序性已满足）。

最终堆

调整后的数组为 [10, 7, 9, 5, 4, 2, 8, 3]，结构如下：

          [10]         ← 根节点最大/    \[7]      [9]      ← 每个父节点 ≥ 子节点/ \      / \[5][4]  [2][8]/[3]

关键点总结

1. heappush 的作用：
   • 在堆的末尾插入新元素，然后通过 heapify_up 调整堆序性。
2. 时间复杂度：
   • append 是 O(1)，heapify_up 是 O(log n)，所以总时间复杂度是 O(log n)。
3. 适用场景：
   • 适用于动态插入元素的场景（如优先队列）。
4. 对比 heappop：
   • heappop 是删除堆顶元素，并用最后一个元素替换，再 heapify_down 调整。

完整代码示例（最大堆）

def heapify_up(heap, i):while i > 0:parent = (i - 1) // 2if heap[i] > heap[parent]:  # 最大堆：子节点 > 父节点则交换heap[i], heap[parent] = heap[parent], heap[i]i = parentelse:breakdef heappush(heap, item):heap.append(item)heapify_up(heap, len(heap) - 1)# 示例用法
heap = [10, 5, 9, 3, 4, 2, 8]
heappush(heap, 7)
print(heap)  # 输出: [10, 7, 9, 5, 4, 2, 8, 3]

4、提取极值

def heappop(heap):if not heap:raise IndexError("heap is empty")root = heap[0]heap[0] = heap[-1]heap.pop()heapify_down(heap, len(heap), 0)return root

heappop 用于删除并返回堆顶元素（最大值或最小值），同时维护堆的性质。它分为以下几步：

1. 检查堆是否为空，若为空则抛出异常。
2. 保存堆顶元素（root = heap），用于最后返回。
3. 将堆末尾元素移到堆顶（heap = heap[-1]），并删除末尾元素（heap.pop()）。
4. 从堆顶开始向下调整（heapify_down），恢复堆序性。

分步图解

假设当前有一个 最大堆，初始数组为 [10, 7, 9, 5, 4, 2, 8, 3]，结构如下：

          [10]         ← 堆顶（待删除）/    \[7]      [9]/ \      / \[5][4]  [2][8]/[3]

Step 1: 删除堆顶并替换为末尾元素

1. 保存堆顶 root = 10（待返回）。
2. 将末尾元素 3 移到堆顶，并删除末尾元素：
   • 数组变为 [3, 7, 9, 5, 4, 2, 8]。

          [3]          ← 新堆顶（原末尾元素3）/    \[7]      [9]/ \      / \[5][4]   [2] [8]

此时堆序性被破坏（3 比子节点 7 和 9 小），需要调整。

Step 2: heapify_down(heap, n=7, i=0)

从堆顶 i=0（节点3）开始下沉：

1. 第一次循环：
   • left = 2*0+1 = 1（节点7），right = 2*0+2 = 2（节点9）。
   • largest 初始为 0（节点3）。
   • 比较 left(7) > largest(3) → largest = left = 1。
   • 比较 right(9) > largest(7) → largest = right = 2。
   • 交换 heap 和 heap（3 ↔ 9），数组变为 [9, 7, 3, 5, 4, 2, 8]。
   • i 更新为 largest = 2（继续检查节点3）。

          [9]          ← 节点9上浮到堆顶/    \[7]      [3]     ← 节点3需要继续下沉/ \      / \[5][4]   [2] [8]

1. 第二次循环：
   • left = 2*2+1 = 5（节点2），right = 2*2+2 = 6（节点8）。
   • largest 初始为 2（节点3）。
   • 比较 left(2) > largest(3)？否。
   • 比较 right(8) > largest(3) → largest = right = 6。
   • 交换 heap 和 heap（3 ↔ 8），数组变为 [9, 7, 8, 5, 4, 2, 3]。
   • i 更新为 largest = 6（继续检查节点3）。

          [9]/    \[7]      [8]     ← 节点8上浮/ \      / \[5][4]   [2] [3]    ← 节点3是叶子节点，无需处理

1. 终止条件：
   • i=6 是叶子节点，largest == i，循环终止。

最终堆

调整后的数组为 [9, 7, 8, 5, 4, 2, 3]，结构如下：

          [9]          ← 新的堆顶/    \[7]      [8]     ← 每个父节点 ≥ 子节点/ \      / \[5][4]   [2] [3]

返回的堆顶元素是 10（已被删除）。

关键点总结

1. heappop 的作用：
   • 删除堆顶元素，并用末尾元素替换，再通过 heapify_down 恢复堆序性。
2. 时间复杂度：
   • pop 和替换是 O(1)，heapify_down 是 O(log n)，总时间复杂度为 O(log n)。
3. 适用场景：
   • 适用于需要动态获取最大值或最小值的场景（如优先队列）。
4. 对比 heappush：
   • heappush 在末尾插入后上浮，heappop 在堆顶删除后下沉。

完整代码示例（最大堆）

def heapify_down(heap, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and heap[left] > heap[largest]:largest = leftif right < n and heap[right] > heap[largest]:largest = rightif largest != i:heap[i], heap[largest] = heap[largest], heap[i]i = largestelse:breakdef heappop(heap):if not heap:raise IndexError("heap is empty")root = heap[0]heap[0] = heap[-1]heap.pop()heapify_down(heap, len(heap), 0)return root# 示例用法
heap = [10, 7, 9, 5, 4, 2, 8, 3]
max_val = heappop(heap)
print("Popped:", max_val)  # 输出: Popped: 10
print("Heap after pop:", heap)  # 输出: Heap after pop: [9, 7, 8, 5, 4, 2, 3]

堆的构建

1. 自顶向下构建（O(n log n)）

def build_heap_slow(items):heap = []for item in items:heappush(heap, item)return heap

build_heap_slow 操作解析（最大堆示例）

build_heap_slow 通过逐个插入元素（heappush）的方式构建堆。虽然逻辑简单，但时间复杂度较高（O(n log n)），因此称为“慢速建堆”。

分步图解

假设输入数组为 [3, 1, 6, 5, 2, 4]，逐步构建最大堆：

初始状态

• heap = []

Step 1: 插入 3

• heappush(heap, 3) → heap =

[3]

Step 2: 插入 1

• heappush(heap, 1) → heap = [3, 1]

   [3]/
[1]

Step 3: 插入 6

1. 先追加到末尾：heap = [3, 1, 6]
2. heapify_up(heap, 2)：
   • 比较 6 和父节点 3（parent = (2-1)//2 = 0），6 > 3 → 交换。
   • heap = [6, 1, 3]

   [6]/   \
[1]   [3]

Step 4: 插入 5

1. 先追加到末尾：heap = [6, 1, 3, 5]
2. heapify_up(heap, 3)：
   • 比较 5 和父节点 1（parent = (3-1)//2 = 1），5 > 1 → 交换。
   • heap = [6, 5, 3, 1]

      [6]/   \[5]    [3]/
[1]

Step 5: 插入 2

1. 先追加到末尾：heap = [6, 5, 3, 1, 2]
2. heapify_up(heap, 4)：
   • 比较 2 和父节点 5（parent = (4-1)//2 = 1），2 ≤ 5 → 停止。

• heap 保持不变：

      [6]/   \[5]    [3]/ \
[1] [2]

Step 6: 插入 4

1. 先追加到末尾：heap = [6, 5, 3, 1, 2, 4]
2. heapify_up(heap, 5)：
   • 比较 4 和父节点 3（parent = (5-1)//2 = 2），4 > 3 → 交换。
   • heap = [6, 5, 4, 1, 2, 3]

      [6]/   \[5]    [4]/ \    /
[1][2] [3]

最终堆

数组为 [6, 5, 4, 1, 2, 3]，结构如下：

      [6]         ← 根节点最大/   \[5]    [4]      ← 每个父节点 ≥ 子节点/ \    /
[1][2] [3]

关键点总结

1. 时间复杂度：
   • 每次 heappush 是 O(log n)，共 n 次操作 → O(n log n)。
2. 空间复杂度：
   • 需要额外空间存储堆 → O(n)。
3. 对比快速建堆（Floyd算法）：
   • 快速建堆直接从最后一个非叶子节点开始 heapify_down，时间复杂度为 O(n)。

完整代码示例（最大堆）

def heapify_up(heap, i):while i > 0:parent = (i - 1) // 2if heap[i] > heap[parent]:  # 最大堆：子节点 > 父节点则交换heap[i], heap[parent] = heap[parent], heap[i]i = parentelse:breakdef heappush(heap, item):heap.append(item)heapify_up(heap, len(heap) - 1)def build_heap_slow(items):heap = []for item in items:heappush(heap, item)return heap# 示例用法
items = [3, 1, 6, 5, 2, 4]
heap = build_heap_slow(items)
print(heap)  # 输出: [6, 5, 4, 1, 2, 3]

优化建议

若需高效建堆，推荐使用 Floyd算法（从最后一个非叶子节点开始 heapify_down）：

def build_heap_fast(items):n = len(items)for i in range((n // 2) - 1, -1, -1):  # 从最后一个非叶子节点开始heapify_down(items, n, i)return items

2. Floyd算法（O(n)）

def build_heap_fast(items):heap = list(items)for i in range(len(heap)//2 - 1, -1, -1):heapify_down(heap, len(heap), i)return heap

build_heap_fast 操作解析（最大堆示例）

build_heap_fast 使用 Floyd算法 在 O(n) 时间内将无序数组直接构建成堆。其核心思想是：从最后一个非叶子节点开始，向前逐个执行 heapify_down。

分步图解

假设输入数组为 [3, 1, 6, 5, 2, 4]，逐步构建最大堆：

Step 1: 初始化

• heap = [3, 1, 6, 5, 2, 4]（直接复制原数组）
• 最后一个非叶子节点的索引：len(heap)//2 - 1 = 2（即节点 6）

Step 2: 从索引 2 开始 heapify_down

1. 处理 i=2（节点6）：
   • 左子节点 left=2*2+1=5（值4），右子节点 right=2*2+2=6（超出范围）。
   • largest=2（节点6），比较 left(4) > largest(6)？否 → 无需交换。
   • 堆保持不变：

         [3, 1, 6, 5, 2, 4]

Step 3: 处理 i=1（节点1）

1. 执行 heapify_down(heap, 6, 1)：
   • 左子节点 left=3（值5），右子节点 right=4（值2）。
   • largest=1（节点1），比较 left(5) > largest(1) → largest=left=3。
   • 比较 right(2) > largest(5)？否 → 保持 largest=3。
   • 交换 heap 和 heap（1 ↔ 5），数组变为 [3, 5, 6, 1, 2, 4]。
   • 继续检查 i=3（节点1），但它是叶子节点，终止。
   • 堆状态：

         [3, 5, 6, 1, 2, 4]

Step 4: 处理 i=0（节点3）

1. 执行 heapify_down(heap, 6, 0)：
   • 左子节点 left=1（值5），右子节点 right=2（值6）。
   • largest=0（节点3），比较 left(5) > largest(3) → largest=left=1。
   • 比较 right(6) > largest(5) → largest=right=2。
   • 交换 heap 和 heap（3 ↔ 6），数组变为 [6, 5, 3, 1, 2, 4]。
   • 继续检查 i=2（节点3）：
     • 左子节点 left=5（值4），右子节点 right=6（超出范围）。
     • 比较 left(4) > largest(3) → largest=left=5。
     • 交换 heap 和 heap（3 ↔ 4），数组变为 [6, 5, 4, 1, 2, 3]。
   • 堆最终状态：

         [6, 5, 4, 1, 2, 3]

最终堆

数组为 [6, 5, 4, 1, 2, 3]，结构如下：

      [6]         ← 根节点最大/   \[5]    [4]      ← 每个父节点 ≥ 子节点/ \    /
[1][2] [3]

关键点总结

1. 时间复杂度：
   • O(n)（Floyd算法比逐个插入的 O(n log n) 更高效）。
2. 空间复杂度：
   • O(1)（原地修改，无需额外空间）。
3. 为什么从 n//2 -1 开始：
   • 叶子节点本身已是合法堆，只需调整非叶子节点。
4. 对比 build_heap_slow：

   方法	时间复杂度	空间复杂度	适用场景
   build_heap_slow	O(n log n)	O(n)	动态插入
   build_heap_fast	O(n)	O(1)	静态数组批量建堆

完整代码示例（最大堆）

def heapify_down(heap, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and heap[left] > heap[largest]:largest = leftif right < n and heap[right] > heap[largest]:largest = rightif largest != i:heap[i], heap[largest] = heap[largest], heap[i]i = largestelse:breakdef build_heap_fast(items):heap = list(items)for i in range(len(heap) // 2 - 1, -1, -1):  # 从最后一个非叶子节点向前heapify_down(heap, len(heap), i)return heap# 示例用法
items = [3, 1, 6, 5, 2, 4]
heap = build_heap_fast(items)
print(heap)  # 输出: [6, 5, 4, 1, 2, 3]

Floyd算法数学原理

1. 建堆复杂度证明：
   • 第 k 层的节点最多需要下沉 h-k 次（h 是堆高度）。
   • 总操作次数 = Σ (节点数 × 下沉次数) = Σ 2ᵏ × (h-k) ≈ O(n)。
2. 为什么快：
   • 越下层的节点越多，但需要调整的次数越少；越上层的节点越少，但调整次数多。两者平衡后为线性复杂度。

堆排序

def heap_sort(arr):# 构建最大堆n = len(arr)for i in range(n//2 - 1, -1, -1):heapify_down(arr, n, i)# 逐个提取元素for i in range(n-1, 0, -1):arr[0], arr[i] = arr[i], arr[0]  # 交换根与末尾heapify_down(arr, i, 0)  # 对缩小后的堆进行调整

heap_sort 操作解析（升序排序示例）

堆排序分为两步：

1. 构建最大堆：将无序数组调整为最大堆结构。
2. 逐个提取最大值：将堆顶（最大值）与末尾交换，缩小堆范围并重新调整。

分步图解

假设输入数组为 [3, 1, 6, 5, 2, 4]，逐步进行堆排序：

Step 1: 构建最大堆

调用 build_heap_fast 后，数组变为 [6, 5, 4, 1, 2, 3]，结构如下：

      [6]         ← 根节点最大/   \[5]    [4]/ \    /
[1][2] [3]

Step 2: 排序阶段

1. 第一次交换（i=5）：
   • 交换 arr 和 arr（6 ↔ 3），数组变为 [3, 5, 4, 1, 2, 6]。
   • 对前 5 个元素 [3, 5, 4, 1, 2] 执行 heapify_down(arr, 5, 0)：
     • 节点 3 与子节点 5 和 4 比较 → 交换 3 和 5 → [5, 3, 4, 1, 2, 6]。
     • 节点 3 继续与子节点 1 和 2 比较 → 交换 3 和 2 → [5, 2, 4, 1, 3, 6]。
   • 当前堆范围 [5, 2, 4, 1, 3]，结构如下：

         [5]/   \[2]   [4]/ \[1][3]

1. 第二次交换（i=4）：
   • 交换 arr 和 arr（5 ↔ 3），数组变为 [3, 2, 4, 1, 5, 6]。
   • 对前 4 个元素 [3, 2, 4, 1] 执行 heapify_down(arr, 4, 0)：
     • 节点 3 与子节点 2 和 4 比较 → 交换 3 和 4 → [4, 2, 3, 1, 5, 6]。
   • 当前堆范围 [4, 2, 3, 1]，结构如下：

         [4]/   \[2]   [3]/[1]

1. 后续交换（i=3, 2, 1）：
   • 类似操作，每次交换堆顶和当前末尾，缩小堆范围并调整。
   • 最终数组变为 [1, 2, 3, 4, 5, 6]（升序排列）。

关键点总结

1. 时间复杂度：
   • 建堆：O(n)。
   • 排序阶段：共 n-1 次交换和调整，每次调整 O(log n) → 总 O(n log n)。
2. 空间复杂度：
   • O(1)（原地排序）。
3. 稳定性：
   • 不稳定（交换可能破坏相同元素的相对顺序）。
4. 对比其他排序：

   排序算法	平均时间复杂度	空间复杂度	稳定性
   堆排序	O(n log n)	O(1)	不稳定
   快速排序	O(n log n)	O(log n)	不稳定
   归并排序	O(n log n)	O(n)	稳定

完整代码示例

def heapify_down(arr, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and arr[left] > arr[largest]:largest = leftif right < n and arr[right] > arr[largest]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]i = largestelse:breakdef heap_sort(arr):n = len(arr)# 构建最大堆for i in range(n//2 - 1, -1, -1):heapify_down(arr, n, i)# 逐个提取最大值for i in range(n-1, 0, -1):arr[0], arr[i] = arr[i], arr[0]  # 交换heapify_down(arr, i, 0)  # 调整缩小后的堆# 示例用法
arr = [3, 1, 6, 5, 2, 4]
heap_sort(arr)
print(arr)  # 输出: [1, 2, 3, 4, 5, 6]

为什么堆排序不如快速排序常用？

1. 缓存不友好：堆排序的跳跃式访问（非连续内存）比快速排序的局部访问慢。
2. 常数因子大：实际运行中，堆排序的常数因子通常比快速排序大。
3. 不稳定：某些场景需要稳定性。

高级堆结构

1. 二项堆

• 由一组二项树组成的森林
• 支持O(1)时间合并

2. 斐波那契堆

• 理论最优的优先级队列
• 插入/合并：O(1)摊还时间
• 提取最小：O(log n)摊还时间

3. 配对堆

• 简单高效的堆结构
• 实践表现优于理论复杂度

实际应用场景

1. 优先级队列

• 操作系统进程调度
• 网络带宽管理

2. 算法优化

• Dijkstra最短路径算法
• Prim最小生成树算法
• Top K问题（前K大/小元素）

3. 事件驱动模拟

• 离散事件模拟系统
• 游戏引擎事件处理

4. 实时系统

• 紧急任务优先处理
• 医疗监控系统警报

Python中的堆模块

import heapq  # 最小堆实现nums = [3, 1, 4, 1, 5, 9, 2, 6]
heap = []# 构建堆
for num in nums:heapq.heappush(heap, num)  # [1, 1, 2, 3, 5, 9, 4, 6]# 访问最小元素
print(heap[0])  # 1 (不弹出)# 弹出最小元素
print(heapq.heappop(heap))  # 1
print(heap)  # [1, 3, 2, 6, 5, 9, 4]# 堆排序
print([heapq.heappop(heap) for _ in range(len(heap))])  # [1, 2, 3, 4, 5, 6, 9]

堆与相关数据结构对比

常见面试问题

1. 实现优先级队列
2. 合并K个有序链表
3. 数据流的中位数（双堆技巧）
4. Top K频繁元素
5. 滑动窗口最大值
6. 最小会议室数量（区间问题）
7. 设计Twitter feed（获取最新推文）
8. 连续中值问题
9. 任务调度器
10. 最便宜的航班（带K次中转）

性能优化技巧

1. 批量建堆：使用Floyd算法而非逐个插入
2. 惰性删除：标记删除而非立即移除，在弹出时跳过
3. 预分配空间：避免动态扩容开销
4. 自定义比较：Python中使用元组或实现__lt__方法
5. 多级堆：分层处理超大规模数据

总结：堆的智慧

堆结构展示了计算机科学中几个核心思想：

• 部分有序：不必完全排序即可高效解决特定问题
• 空间-时间权衡：用数组紧凑存储树结构
• 优先级抽象：将复杂决策简化为极值选择

掌握堆的关键在于：

1. 理解完全二叉树与数组的映射关系
2. 熟练上浮/下沉操作的内在逻辑
3. 识别适合堆解决的问题模式
4. 了解不同语言的标准库实现

记住：当问题涉及"极值"、"优先级"或"动态排序"时，堆往往是最优雅高效的解决方案。这种数据结构不仅存在于算法竞赛中，更广泛应用于各种生产系统，是现代软件开发不可或缺的工具之一。