17370845950

Python通过heapq模块实现最小堆，可对列表进行堆化、插入、弹出等操作，支持高效获取极值及模拟最大堆。

Python 中没有专门的“堆”类型，但可以通过内置模块 heapq 来创建和使用堆。heapq 模块提供了对列表进行堆操作的函数，实现的是最小堆（min-heap）结构。

1. 创建堆

堆在 Python 中本质上是一个普通列表，通过 heapq 提供的函数维护堆的性质。

使用 heapq.heapify() 可将一个无序列表转换为最小堆：

• 原地修改列表，不返回新对象
• 时间复杂度为 O(n)

import heapq
data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data)
print(data)  # 输出: [1, 1, 2, 3, 5, 9, 4, 6]（满足最小堆结构）

2. 插入元素（入堆）

使用 heapq.heappush(heap, item) 向堆中添加元素：

• 保持堆结构不变
• 时间复杂度为 O(log n)

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heap)  # 输出: [1, 3, 4]

3. 弹出最小元素（出堆）

使用 heapq.heappop(heap) 弹出并返回堆顶（最小值）：

• 弹出后自动调整堆结构
• 常用于获取当前最小元素

min_val = heapq.heappop(heap)
print(min_val)  # 输出: 1
print(heap)     # 输出: [3, 4]

4. 其他常用操作

heapq 还提供一些实用函数：

• heappushpop(heap, item)：先入堆再弹出最小值，效率高于分开调用
• heapreplace(heap, item)：先弹出最小值，再入堆，堆大小不变
• nlargest(n, iterable)：获取最大 n 个元素
• nsmallest(n, iterable)：获取最小 n 个元素

# 示例：获取最小的两个数
nums = [5, 1, 8, 3, 9]
two_smallest = heapq.nsmallest(2, nums)
print(two_smallest)  # 输出: [1, 3]

若需要最大堆，可通过取负值模拟：

max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
largest = -heapq.heappop(max_heap)
print(largest)  # 输出: 20

基本上就这些。heapq 简单高效，适合实现优先队列、求 TopK、合并多路有序序列等场景。