什么是堆数据结构？

堆（Heap）是一种特殊的树形数据结构，满足以下性质：

• 堆是一个完全二叉树
• 堆中每个节点的值都大于等于（最大堆）或小于等于（最小堆）其子节点的值

Python的heapq模块实现了最小堆，即父节点的值总是小于或等于其子节点的值。

heapq模块核心函数

heapq基础使用示例

import heapq

# 创建一个列表
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# 将列表转换为堆（原地转换）
heapq.heapify(data)
print("堆结构:", data)  # 输出: [1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

# 向堆中添加元素
heapq.heappush(data, 0)
print("添加0后:", data)  # 输出: [0, 1, 1, 3, 3, 2, 4, 6, 5, 5, 5, 9]

# 从堆中弹出最小元素
min_val = heapq.heappop(data)
print("弹出元素:", min_val)  # 输出: 0
print("弹出后堆:", data)    # 输出: [1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

import heapq

heap = [2, 5, 7, 9]
heapq.heapify(heap)

# heappushpop: 先push再pop
result = heapq.heappushpop(heap, 3)
print("heappushpop结果:", result)  # 输出: 2
print("当前堆:", heap)            # 输出: [3, 5, 7, 9]

# heapreplace: 先pop再push
result = heapq.heapreplace(heap, 4)
print("heapreplace结果:", result)  # 输出: 3
print("当前堆:", heap)             # 输出: [4, 5, 7, 9]

import heapq

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# 查找最小的3个元素
smallest = heapq.nsmallest(3, numbers)
print("最小的3个元素:", smallest)  # 输出: [1, 1, 2]

# 查找最大的3个元素
largest = heapq.nlargest(3, numbers)
print("最大的3个元素:", largest)  # 输出: [9, 6, 5]

实际应用场景

import heapq

def heap_sort(iterable):
    heap = []
    for value in iterable:
        heapq.heappush(heap, value)
    return [heapq.heappop(heap) for _ in range(len(heap))]

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_data = heap_sort(data)
print("堆排序结果:", sorted_data)  # 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0  # 用于处理相同优先级的元素顺序
    
    def push(self, item, priority):
        # 使用(priority, index, item)元组确保相同优先级下插入顺序
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1
    
    def pop(self):
        return heapq.heappop(self._queue)[-1]  # 返回元组的最后一个元素（item）
    
    def is_empty(self):
        return len(self._queue) == 0

# 使用示例
pq = PriorityQueue()
pq.push('任务A', 3)
pq.push('任务B', 1)
pq.push('任务C', 2)
pq.push('任务D', 1)  # 与任务B相同优先级

while not pq.is_empty():
    print(pq.pop())  # 输出: 任务B, 任务D, 任务C, 任务A

import heapq

def top_k_largest(nums, k):
    # 使用最小堆来存储k个最大元素
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        else:
            # 如果当前数大于堆顶（最小值），则替换
            if num > heap[0]:
                heapq.heapreplace(heap, num)
    return heap

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 4
result = top_k_largest(data, k)
print(f"最大的{k}个元素:", sorted(result, reverse=True))  # 输出: [9, 6, 5, 5]

使用注意事项

• heapq模块只提供最小堆实现，如需最大堆，可以将元素取负值后使用
• 堆中元素可以是元组，heapq按元组第一个元素比较，这常用于实现优先级队列
• heapify操作的时间复杂度是O(n)，而不是O(n log n)
• 当处理大型数据集时，nlargest和nsmallest比排序整个列表更高效
• 堆操作后，列表的第一个元素总是最小的（heap[0]）
• heapq模块不是线程安全的，多线程环境下需要加锁

总结

heapq模块是Python标准库中用于堆操作的高效工具，特别适合处理优先级队列、Top K问题和堆排序等场景。

关键要点：

• 使用heapify()将列表转换为堆
• 使用heappush()和heappop()进行元素添加和删除
• 组合操作heappushpop()和heapreplace()更高效
• 使用nlargest()和nsmallest()获取最大/最小的N个元素
• 堆结构非常适合解决优先级队列和Top K问题

提示： 当需要处理大量数据时，堆操作的时间复杂度优势会非常明显，特别是O(n log k)的操作相比于O(n log n)的全排序可以节省大量时间和内存。