heapq.heapify构建小顶堆的流程
代码示例
import heapqlst = [2, 3, 4, 6, 9, 1, 5]
heapq.heapify(lst)
print(lst)
流程解释
-
初始列表:
- 列表
lst在开始时是[2, 3, 4, 6, 9, 1, 5]。
- 列表
-
调用
heapq.heapify(lst):heapify函数将lst转换为一个小顶堆（min-heap）。- 在小顶堆中，任意一个父节点的值都小于或等于其子节点的值。
-
如何构建小顶堆:
- 从最后一个非叶子节点开始，逐个向上进行“下沉”操作（sift down），调整节点以满足堆的性质。
- 对于列表的索引和树形结构的关系：对于索引
i的节点，其左子节点在2*i + 1，右子节点在2*i + 2。
实际步骤：
-
初始列表:
2 ├── 3 ├── 4 ├── 6 ├── 9 ├── 1 └── 5 -
从最后一个非叶子节点开始:
- 最后一个非叶子节点索引为
len(lst)//2 - 1（对于这个例子，索引为2，值为4）。
- 最后一个非叶子节点索引为
-
处理索引 2（值 4）:
- 左子节点为
1（索引 5），右子节点为5（索引 6）。 1是最小的，交换 4 和 1:
2 ├── 3 ├── 1 ├── 6 ├── 9 └── 4 └── 5 - 左子节点为
-
处理索引 1（值 3）:
- 左子节点
6（索引 3），右子节点9（索引 4）。 - 没有交换，因为
3小于它的子节点。
- 左子节点
-
处理索引 0（值 2）:
- 左子节点
3（索引 1），右子节点1（索引 2）： - 最小的是
1，交换2和1:
1 ├── 3 ├── 2 ├── 6 ├── 9 └── 4 └── 5 - 左子节点
-
最终输出:
- 完成后，
lst变为[1, 3, 2, 6, 9, 4, 5]。 - 但是为了符合最小堆的性质，最终顺序可能需要调整（可能还需要进一步的下沉）。
- 完成后，
完整堆的结果应该是:
运行后 lst 会变为 [1, 3, 2, 6, 9, 4, 5]，并且这是最小堆的结构。
总结
heapq.heapify 的作用是将一个列表变为小顶堆，其核心在于“下沉”操作，确保每个父节点的值都小于或等于任何子节点的值。这种操作的时间复杂度为 O(n)。完成后，你可以通过 heapq.heappop 等操作获取元素，仍然会保持堆的特性。