Python​​ heapq 构造大顶堆

Guan_Zhu · 2023-02-04 14:55:32 · 个人记录

前言

大家都知道 Python 的 heapq 只能构造小顶堆，下面我将介绍一种在 Python 使用 heapq 构造大顶堆的方法。堆作为优先队列的常用方法，而且在数据结构和算法方面，经常使用大顶堆和小顶堆进行问题的解决。

代码实现

默认的堆结构是小顶堆，heapq里没有直接构造大顶堆的方法，首先我们进行构造堆结构，要在每一个元素前增加一个负号

nums = [2, 5, 1, 6, 9, 0]
heap = []
for num in heap:
heapq.heappush(heap, -num)
print([-heapq.heappop(heap) for _ in range(len(nums))])

输出：

[9, 6, 5, 2, 1, 0]

这样就将大顶堆输出出来了。