heapq.heapify构建小顶堆的流程

代码示例

import heapq

lst = [2, 3, 4, 6, 9, 1, 5]
heapq.heapify(lst)
print(lst)
1
2
3
4
5

流程解释

1. 初始列表:

   • 列表 lst 在开始时是 [2, 3, 4, 6, 9, 1, 5]。

2. 调用 heapq.heapify(lst):

   • heapify 函数将 lst 转换为一个小顶堆（min-heap）。
   • 在小顶堆中，任意一个父节点的值都小于或等于其子节点的值。

3. 如何构建小顶堆:

   • 从最后一个非叶子节点开始，逐个向上进行“下沉”操作（sift down），调整节点以满足堆的性质。
   • 对于列表的索引和树形结构的关系：对于索引 i 的节点，其左子节点在 2*i + 1，右子节点在 2*i + 2。

实际步骤：

• 初始列表:

  2
  ├── 3
  ├── 4
  ├── 6
  ├── 9
  ├── 1
  └── 5
  1
  2
  3
  4
  5
  6
  7

• 从最后一个非叶子节点开始:

  • 最后一个非叶子节点索引为 len(lst)//2 - 1（对于这个例子，索引为 2，值为 4）。

1. 处理索引 2（值 4）:

   • 左子节点为 1（索引 5），右子节点为 5（索引 6）。
   • 1 是最小的，交换 4 和 1:

   2
   ├── 3
   ├── 1
   ├── 6
   ├── 9
   └── 4
   └── 5
   1
   2
   3
   4
   5
   6
   7

2. 处理索引 1（值 3）:

   • 左子节点 6（索引 3），右子节点 9（索引 4）。
   • 没有交换，因为 3 小于它的子节点。

3. 处理索引 0（值 2）:

   • 左子节点 3（索引 1），右子节点 1（索引 2）：
   • 最小的是 1，交换 2 和 1:

   1
   ├── 3
   ├── 2
   ├── 6
   ├── 9
   └── 4
   └── 5
   1
   2
   3
   4
   5
   6
   7

4. 最终输出:

   • 完成后，lst 变为 [1, 3, 2, 6, 9, 4, 5]。
   • 但是为了符合最小堆的性质，最终顺序可能需要调整（可能还需要进一步的下沉）。
     

完整堆的结果应该是:

运行后 lst 会变为 [1, 3, 2, 6, 9, 4, 5]，并且这是最小堆的结构。

总结

heapq.heapify 的作用是将一个列表变为小顶堆，其核心在于“下沉”操作，确保每个父节点的值都小于或等于任何子节点的值。这种操作的时间复杂度为 O(n)。完成后，你可以通过 heapq.heappop 等操作获取元素，仍然会保持堆的特性。