Python heapq 实现大顶堆详解

在 Python 标准库中，heapq 模块提供了堆（Heap）的实现，但默认只支持小顶堆（最小堆）。本文将详细介绍如何利用 heapq 实现大顶堆（最大堆），并提供实用示例和技巧。

什么是大顶堆？

大顶堆是一种特殊的完全二叉树，其中任意父节点的值都大于或等于其子节点的值。堆顶（根节点）即为整个堆中的最大值。

为什么 heapq 默认是小顶堆？

heapq 是基于列表实现的最小堆，所有操作（如 heappush、heappop）都保证堆顶是最小元素。这是由其底层算法决定的。

实现大顶堆的常用方法

方法一：取负值法（推荐）

由于 Python 的整数可以取负，我们可以通过插入元素的相反数来“反转”大小关系：

# 示例：使用负值模拟大顶堆
import heapq

max_heap = []
data = [3, 1, 4, 1, 5]

# 插入时取负
for num in data:
    heapq.heappush(max_heap, -num)

# 弹出时再取负还原
while max_heap:
    print(-heapq.heappop(max_heap))
# 输出：5, 4, 3, 1, 1

方法二：封装类（面向对象）

通过自定义类重写比较方法，使 heapq 在比较时“反向”判断：

import heapq

class MaxHeapObj:
    def __init__(self, val):
        self.val = val
    def __lt__(self, other):
        return self.val > other.val  # 反向比较
    def __eq__(self, other):
        return self.val == other.val
    def __str__(self):
        return str(self.val)

# 使用示例
max_heap = []
heapq.heappush(max_heap, MaxHeapObj(3))
heapq.heappush(max_heap, MaxHeapObj(1))
heapq.heappush(max_heap, MaxHeapObj(4))

while max_heap:
    print(heapq.heappop(max_heap).val)
# 输出：4, 3, 1

常见应用场景

• 求 Top-K 最大元素（如排行榜）
• 优先级队列（高优先级先处理）
• 滑动窗口最大值问题（配合其他数据结构）

性能与注意事项

• heapq 的 push 和 pop 操作时间复杂度均为 O(log n)
• 大顶堆不是内置类型，请勿直接对原生列表调用 heapify 后期望它是大顶堆
• 多线程环境下需加锁，heapq 本身非线程安全

总结

虽然 Python 的 heapq 只原生支持小顶堆，但通过取负值或自定义比较类，我们可以轻松实现大顶堆的功能。在实际开发中，取负值法因其简洁高效而被广泛采用。