深入理解Python堆数据结构（从零开始掌握heapq模块与堆排序算法）

Python 的 heapq 模块默认实现的是最小堆。如果你需要最大堆，可以通过对元素取负值来间接实现。

使用 heapq 模块操作堆

首先，导入 heapq 模块：

import heapq

1. 创建堆

你可以从一个普通列表创建堆，使用 heapify() 函数将其转换为堆结构（就地操作，时间复杂度 O(n)）：

import heapq# 初始化一个普通列表nums = [5, 7, 9, 1, 3]# 转换为最小堆heapq.heapify(nums)print(nums)  # 输出可能是 [1, 3, 9, 7, 5]（具体顺序取决于内部结构）

2. 插入元素

使用 heappush(heap, item) 向堆中插入新元素：

heapq.heappush(nums, 2)print(nums)  # 堆自动调整，保持最小堆性质

3. 弹出最小元素

使用 heappop(heap) 弹出并返回堆顶（最小）元素：

min_val = heapq.heappop(nums)print(min_val)  # 输出 1print(nums)     # 剩余元素仍保持堆结构

实战：用堆实现堆排序

利用堆的特性，我们可以轻松实现堆排序算法。步骤如下：

1. 将列表转为最小堆；
2. 不断弹出堆顶元素，按顺序收集即可得到升序序列。

def heap_sort(arr):    heapq.heapify(arr)    sorted_list = []    while arr:        sorted_list.append(heapq.heappop(arr))    return sorted_list# 测试original = [12, 3, 5, 7, 19, 1]sorted_result = heap_sort(original.copy())print("原始数组:", original)print("排序后:", sorted_result)# 输出：排序后: [1, 3, 5, 7, 12, 19]

如何实现最大堆？

由于 heapq 只支持最小堆，我们可以通过存储元素的负值来模拟最大堆：

# 模拟最大堆max_heap = []for num in [3, 1, 4, 1, 5]:    heapq.heappush(max_heap, -num)  # 存入负值# 弹出最大值（需再取负）max_val = -heapq.heappop(max_heap)print(max_val)  # 输出 5

总结

通过本教程，你已经掌握了：

• Python堆数据结构的基本原理；
• 如何使用 heapq 模块进行堆操作；
• 如何实现高效的堆排序算法；
• 如何变通实现最大堆。

堆是算法面试和工程实践中非常实用的数据结构。熟练掌握 heapq模块 和 最小堆实现，将大大提升你解决优先级调度、Top-K 问题等场景的能力。

现在就动手试试吧！用堆优化你的下一个Python项目。