在Python中，堆（Heap）是一种特殊的完全二叉树结构，满足以下特性：
最大堆（Max Heap）：父节点的值大于或等于子节点的值。
最小堆（Min Heap）：父节点的值小于或等于子节点的值。
Python标准库 heapq 提供了一个 最小堆 的实现，虽然没有直接提供最大堆的实现，但是可以通过一些技巧实现最大堆。
1. heapq 模块
heapq 是 Python 提供的堆相关操作的模块，它实现了一个最小堆。主要提供以下几个操作：
heapq.heappush(heap, item)：将元素 item 添加到堆 heap 中。
heapq.heappop(heap)：弹出堆中最小的元素并返回。
heapq.heapify(iterable)：将可迭代对象 iterable 转换为堆。
heapq.heappushpop(heap, item)：将元素 item 添加到堆中，并弹出最小元素。
heapq.heapreplace(heap, item)：弹出堆中最小的元素并将元素 item 加入堆中。
2. 例子：最小堆操作
import heapq
# 初始化堆
heap = []
# 插入元素
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
heapq.heappush(heap, 15)
# 弹出最小元素
print(heapq.heappop(heap)) # 10
# 查看堆的最小元素但不弹出
print(heap[0]) # 15
3. 例子：最大堆的实现（通过取负值）
Python的 heapq 默认是最小堆，但可以通过取负数来模拟最大堆：
import heapq
# 初始化最大堆
max_heap = []
# 插入元素，取负值
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -15)
# 弹出最大元素（实际上弹出的是最小负数，恢复负值后就是最大数）
print(-heapq.heappop(max_heap)) # 20
4. 堆排序
堆排序是通过堆来进行排序的，主要过程是先将数组转换为堆，再将堆顶元素弹出并将堆重新调整，直到所有元素都排好。
import heapq
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
# 堆排序，首先将数组转为堆
heapq.heapify(arr)
# 然后弹出堆顶元素，逐一得到排序后的结果
sorted_arr = [heapq.heappop(arr) for _ in range(len(arr))]
print(sorted_arr) # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
5. 常见算法题中的堆应用
5.1 寻找第K大的元素
给定一个无序的数组，找到第 K 大的元素。我们可以使用最小堆来解决这个问题。
import heapq
def findKthLargest(nums, k):
# 构建一个包含前k个元素的最小堆
heap = nums[:k]
heapq.heapify(heap)
# 遍历剩余元素
for num in nums[k:]:
# 如果当前元素大于堆顶元素（最小的元素）
if num > heap[0]:
heapq.heappushpop(heap, num)
# 堆顶元素就是第K大的元素
return heap[0]
5.2 合并K个排序链表
假设有多个已经排序的链表，合并它们。我们可以使用最小堆来解决这个问题。
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __lt__(self, other):
return self.val < other.val
def mergeKLists(lists):
heap = []
# 初始化堆，将所有链表的头节点加入堆
for l in lists:
if l:
heapq.heappush(heap, l)
# 创建一个新的虚拟头节点
dummy = ListNode()
cur = dummy
# 合并链表
while heap:
node = heapq.heappop(heap)
cur.next = node
cur = cur.next
if node.next:
heapq.heappush(heap, node.next)
return dummy.next
5.3 查找前K个频繁元素
给定一个字符串，要求返回出现频率前K高的字符。
import heapq
from collections import Counter
def topKFrequent(nums, k):
# 统计频率
count = Counter(nums)
# 使用最小堆存储频率和对应的元素
heap = []
for key, value in count.items():
heapq.heappush(heap, (value, key))
if len(heap) > k:
heapq.heappop(heap)
# 返回结果
return [item[1] for item in heap]
6. 总结
Python 的 heapq 默认实现最小堆。
可以通过插入负数来模拟最大堆。
堆广泛应用于以下类型的问题：
找到第 K 大/小的元素。
合并多个排序序列。
频率统计问题。
使用堆时可以通过适当的操作（如 heapq.heappush、heapq.heappop）来高效地管理和访问数据结构中的最小或最大元素。
