8.1 堆的完全二叉树结构与堆序性质
堆是一种特殊的完全二叉树，它有两个关键特性：完全二叉树结构和堆序性质。完全二叉树意味着除了最后一层，其他层都是满的，而且最后一层的节点都靠左排列。堆序性质则分为两种：最小堆（父节点值小于等于子节点值）和最大堆（父节点值大于等于子节点值）。
这种结构让堆在数组中能高效存储——对于索引为 i 的节点，其左子节点在 2i+1，右子节点在 2i+2，父节点在 (i-1)//2。这使得堆的操作时间复杂度很优秀，比如插入和删除都是 O(log n)。
堆的核心价值在于能快速获取最值（最小或最大），这在优先队列、Top-K 问题等场景中非常实用。记住，堆不是排序结构，它只保证堆顶是最值，其他元素的顺序是不确定的。
8.2 最小堆与最大堆的数组表示
堆通常用数组来表示，因为完全二叉树的特性让数组索引能直接映射到树的节点位置。最小堆的数组表示中，堆顶（索引 0）是最小元素；最大堆的数组表示中，堆顶是最大元素。
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| 创建最小堆 | heap = [] | 初始化空列表，后续用 heapq 操作保持最小堆性质 |
| 创建最大堆 | heap = [] | Python heapq 默认是最小堆，最大堆需存负值或自定义比较 |
| 数组转堆 | heapq.heapify(arr) | 将列表原地转换为最小堆，时间复杂度 O(n) |
下面是一个简单的示例，展示如何用数组表示最小堆并验证其结构：
python
import heapq
# 初始化一个列表作为堆的底层存储
heap_array = [3, 1, 4, 1, 5, 9, 2, 6]
# 使用 heapq.heapify 将列表转换为最小堆（原地操作）
# heapq 是 Python 标准库，提供堆操作函数，默认实现最小堆
heapq.heapify(heap_array)
# 打印堆数组，验证堆序性质（堆顶是最小值）
print("最小堆数组表示:", heap_array) # 输出类似 [1, 1, 2, 3, 5, 9, 4, 6]
# 验证完全二叉树结构：对于索引 i，左子=2*i+1，右子=2*i+2
def verify_heap_structure(heap):
"""验证堆的完全二叉树结构和堆序性质"""
n = len(heap)
for i in range(n):
left = 2 * i + 1
right = 2 * i + 2
# 检查左子节点是否满足堆序（最小堆：父 <= 左子）
if left < n and heap[i] > heap[left]:
return False, f"索引 {i} 和左子 {left} 违反堆序"
# 检查右子节点是否满足堆序（最小堆：父 <= 右子）
if right < n and heap[i] > heap[right]:
return False, f"索引 {i} 和右子 {right} 违反堆序"
return True, "堆结构和堆序性质正确"
# 调用验证函数
is_valid, message = verify_heap_structure(heap_array)
print("堆验证结果:", message)注意事项：
- Python 的
heapq模块只直接支持最小堆。如果需要最大堆，通常的做法是存储元素的负值（例如，存 -x 而不是 x），这样最小堆的行为就等价于最大堆。 heapq.heapify()是原地操作，会修改原列表，时间复杂度是 O(n)，比逐个插入（O(n log n)）更高效。- 堆的数组表示必须严格遵循完全二叉树的索引规则，否则堆操作会出错。
8.3 上浮（sift-up）与下沉（sift-down）操作
上浮（sift-up）和下沉（sift-down）是堆的核心操作，用于维护堆序性质。当新元素插入堆底时，可能破坏堆序，需要通过上浮将其移到正确位置；当堆顶元素被移除后，需要将最后一个元素移到堆顶并通过下沉调整到正确位置。
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| 插入元素（触发上浮） | heapq.heappush(heap, item) | 向堆中添加元素，自动上浮维护堆序，时间复杂度 O(log n) |
| 弹出堆顶（触发下沉） | heapq.heappop(heap) | 移除并返回堆顶元素，自动下沉维护堆序，时间复杂度 O(log n) |
| 替换堆顶 | heapq.heapreplace(heap, item) | 先弹出堆顶再插入新元素，比 heappop+heappush 更高效 |
下面是一个手动实现上浮和下沉操作的示例（虽然实际中我们用 heapq，但理解原理很重要）：
python
def sift_up(heap, index):
"""上浮操作：将索引 index 的元素上浮到正确位置（最小堆）"""
# 当前元素不是根节点时循环
while index > 0:
parent_index = (index - 1) // 2 # 计算父节点索引
# 如果当前元素 >= 父元素，堆序已满足，停止上浮
if heap[index] >= heap[parent_index]:
break
# 否则交换当前元素和父元素
heap[index], heap[parent_index] = heap[parent_index], heap[index]
index = parent_index # 更新当前索引为父索引，继续上浮
def sift_down(heap, start, end):
"""下沉操作：将索引 start 的元素下沉到正确位置（最小堆），end 是堆的边界"""
root = start
while True:
child = 2 * root + 1 # 左子节点索引
# 如果左子节点超出边界，说明当前节点是叶子，停止下沉
if child > end:
break
# 找到左右子节点中的较小者（如果有右子节点且更小）
if child + 1 <= end and heap[child + 1] < heap[child]:
child += 1
# 如果当前节点 <= 较小子节点，堆序已满足，停止下沉
if heap[root] <= heap[child]:
break
# 否则交换当前节点和较小子节点
heap[root], heap[child] = heap[child], heap[root]
root = child # 更新当前索引为子节点索引，继续下沉
# 示例：手动模拟堆操作
manual_heap = [1, 3, 2, 6, 5, 4] # 假设这是一个部分有效的最小堆
# 模拟插入新元素 0（应该上浮到堆顶）
manual_heap.append(0)
sift_up(manual_heap, len(manual_heap) - 1)
print("插入 0 后上浮结果:", manual_heap) # 应该是 [0, 3, 1, 6, 5, 4, 2]
# 模拟弹出堆顶（0），将最后一个元素移到堆顶并下沉
popped = manual_heap[0]
manual_heap[0] = manual_heap[-1]
manual_heap.pop()
sift_down(manual_heap, 0, len(manual_heap) - 1)
print("弹出堆顶后下沉结果:", manual_heap) # 应该恢复最小堆性质注意事项：
- 上浮操作通常在插入新元素时触发，从堆底开始向上比较和交换。
- 下沉操作通常在移除堆顶元素时触发，从堆顶开始向下比较和交换。
- 手动实现时要注意边界条件，比如根节点没有父节点，叶子节点没有子节点。
- Python 的
heapq内部已经优化了这些操作，实际开发中应优先使用标准库。
8.4 堆在 Top-K 与合并 K 个有序列表中的应用
堆在解决 Top-K 问题（找最大的 K 个元素或最小的 K 个元素）和合并 K 个有序列表时非常高效。Top-K 问题可以用大小为 K 的堆来解决，时间复杂度 O(n log K)；合并 K 个有序列表可以用最小堆维护每个列表的当前最小元素，时间复杂度 O(N log K)，其中 N 是所有元素总数。
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| Top-K 最大元素 | heapq.nlargest(k, iterable) | 直接获取最大的 K 个元素，内部用最小堆实现 |
| Top-K 最小元素 | heapq.nsmallest(k, iterable) | 直接获取最小的 K 个元素，内部用最大堆实现 |
| 合并 K 个有序列表 | 自定义堆存储 (值, 列表索引, 元素索引) | 需要跟踪每个列表的当前位置，避免重复或遗漏 |
下面是一个 Top-K 问题的示例和一个合并 K 个有序列表的示例：
python
import heapq
# 示例1: Top-K 问题（找最大的 3 个元素）
numbers = [10, 4, 5, 8, 1, 9, 3, 7, 2, 6]
k = 3
# 方法1: 使用 heapq.nlargest（推荐，简洁高效）
top_k_largest = heapq.nlargest(k, numbers)
print(f"最大的 {k} 个元素: {top_k_largest}") # 输出 [10, 9, 8]
# 方法2: 手动用最小堆实现 Top-K（理解原理）
min_heap_for_topk = []
for num in numbers:
if len(min_heap_for_topk) < k:
heapq.heappush(min_heap_for_topk, num) # 堆未满，直接插入
else:
# 堆已满，如果当前元素比堆顶大，则替换堆顶
if num > min_heap_for_topk[0]:
heapq.heapreplace(min_heap_for_topk, num)
# 注意：手动实现的结果是无序的，需要排序才能和 nlargest 一致
print(f"手动 Top-K 结果（无序）: {min_heap_for_topk}")
# 示例2: 合并 K 个有序列表
sorted_lists = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
]
def merge_k_sorted_lists(lists):
"""合并 K 个有序列表，返回一个有序列表"""
min_heap = []
result = []
# 初始化堆：将每个列表的第一个元素加入堆
# 堆中存储元组 (值, 列表索引, 元素在列表中的索引)
for i, lst in enumerate(lists):
if lst: # 确保列表非空
heapq.heappush(min_heap, (lst[0], i, 0))
# 不断从堆中取出最小元素，并将对应列表的下一个元素加入堆
while min_heap:
val, list_idx, elem_idx = heapq.heappop(min_heap)
result.append(val)
# 如果对应列表还有下一个元素，加入堆
if elem_idx + 1 < len(lists[list_idx]):
next_val = lists[list_idx][elem_idx + 1]
heapq.heappush(min_heap, (next_val, list_idx, elem_idx + 1))
return result
merged_list = merge_k_sorted_lists(sorted_lists)
print("合并后的有序列表:", merged_list) # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]注意事项：
heapq.nlargest和heapq.nsmallest在 K 较小时非常高效，但如果 K 接近 n，直接排序（sorted(iterable)[-k:]）可能更快。- 合并 K 个有序列表时，堆中存储的元组必须包含足够的信息（值、列表索引、元素索引），以便知道从哪个列表取下一个元素。
- 堆的应用场景很多，但核心思想都是利用堆能快速获取最值的特性，将问题转化为维护一个动态的最值集合。