堆是完全二叉树，分最小堆和最大堆，根节点为最小或最大值；Python用heapq模块实现最小堆，通过heappush、heappop等操作维护堆性质，常用于优先队列、Top K问题和堆排序，最大堆可用负数技巧模拟。
堆是一种特殊的树形数据结构，通常基于完全二叉树实现，最常用的是二叉堆。在Python中，堆常用于实现优先队列，能够高效地获取最小或最大元素。
堆的基本性质
堆分为两种类型：最小堆（min-heap）和最大堆（max-heap）。
- 在最小堆中，父节点的值总是小于或等于其子节点，根节点是整个堆中的最小值。
- 在最大堆中，父节点的值总是大于或等于其子节点，根节点是整个堆中的最大值。
- 堆是一棵完全二叉树，意味着除了最后一层外，其他层都被完全填满，且最后一层从左到右填充。
Python中的堆实现
Python标准库提供了heapq模块，它实现了最小堆的功能。该模块操作的是普通的列表，通过特定函数维护堆的性质。
常见操作包括：
立即学习“Python免费学习笔记（深入）”；
- heapq.heappush(heap, item)：将元素插入堆中，并保持堆结构。
- heapq.heappop(heap)：弹出并返回堆中最小元素，同时维护堆结构。
- heapq.heapify(list)：将一个列表原地转换为堆，时间复杂度为O(n)。
- heapq.heappushpop(heap, item)：先push再pop，效率高于分开调用。
- heapq.heapreplace(heap, item)：先pop最小元素，再push新元素。
注意：heapq只支持最小堆。若需要最大堆，可通过取负值的方式模拟，例如将-item存入堆中。
堆的典型应用场景
堆适用于需要频繁访问极值但不关心整体排序的场景。
- 优先队列：任务按优先级处理，每次取出最高优先级（最小或最大）任务。
- 求第k大/小元素：使用大小为k的堆可高效解决，如Top K问题。
- 合并多个有序序列：利用堆快速选出当前最小元素。
- 堆排序：基于堆结构进行排序，时间复杂度稳定为O(n log n)。
简单示例
下面是一个使用heapq的小例子：
import heapqdata = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(data)
print(heapq.heappop(data)) # 输出 1
heapq.heappush(data, 0)
print(heapq.heappop(data)) # 输出 0
基本上就这些。掌握堆的关键在于理解其结构性质和操作逻辑，结合heapq模块能快速应用于实际问题中。虽然接口简单，但在算法题和系统设计中非常实用。不复杂但容易忽略细节，比如最大堆的负数技巧。
