Python heapq库核心功能与实战案例详解

Python heapq

heapq 是 Python 标准库的重要组成部分，主要提供构建小顶堆（min-heap）的接口及基础操作，如入堆（heappush）和出堆（heappop）等，常用于实现堆排序算法。

堆是一种基于完全二叉树的基本数据结构，满足堆性质：除叶节点外，每个父节点的值均大于等于（大顶堆）或小于等于（小顶堆）其子节点的值。

堆结构分为大顶堆和小顶堆，Python 的 heapq 库默认使用小顶堆：

1. 大顶堆：每个非叶节点的值大于等于其子节点，根节点为最大值。
2. 小顶堆：每个非叶节点的值小于等于其子节点，根节点为最小值。

heapq 内部使用 Python 列表（list）存储数据。为满足堆性质，列表中索引 k 对应的值必须小于等于索引 2k+1 和 2k+2 的值（对应完全二叉树中父节点与子节点的关系）。读者可查阅 heapq 源码以了解其具体实现，源码逻辑较为简洁。

使用Python实现堆排序可以参考：https://www.jb51.net/article/222484.htm

完全二叉树的特性可以参考：https://www.jb51.net/article/222487.htm

一、使用 heapq 创建堆

import heapq 
 
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
    heapq.heappush(heap, num)
print("array:", array)
print("heap: ", heap)
 
heapq.heapify(array)
print("array:", array)

运行结果：

array: [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] heap: [5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50] array: [5, 7, 21, 10, 17, 24, 27, 45, 15, 30, 36, 50]

heapq 中创建堆主要有两种方法：

heappush(heap, num)：先初始化一个空堆，然后逐个将元素插入。每次插入后，堆结构仍保持小顶堆性质。

heapify(array)：直接将现有列表原地调整为小顶堆（调整逻辑参考前述堆排序文章，heapq 已封装实现）。

两种方法生成的堆结构可能不同，例如使用 heappush(heap, num) 得到的堆结构如下。

使用heapify(array)得到的堆结构如下。

尽管结构不同，但两者均满足小顶堆性质，不影响正常使用（堆操作仅从堆顶取值，取值后会自动调整结构）。

二、使用 heapq 实现堆排序

array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
    heapq.heappush(heap, num)
print(heap[0])
# print(heapq.heappop(heap))
heap_sort = [heapq.heappop(heap) for _ in range(len(heap))]
print("heap sort result: ", heap_sort)

运行结果：

5 heap sort result: [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

堆排序步骤：先将待排序列表构建为小顶堆，打印堆顶元素（即最小值）；随后依次调用 heappop 取出堆顶元素并加入新列表，直至堆为空，新列表即为排序结果。

heappop(heap)：移除并返回堆顶元素，同时将剩余元素重新调整为新的小顶堆。

三、获取堆中的最小值或最大值

array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heapq.heapify(array)
print(heapq.nlargest(2, array))
print(heapq.nsmallest(3, array))

运行结果：

[50, 45] [5, 7, 10]

nlargest(num, heap)：从堆中取出 num 个最大元素，按从大到小顺序返回列表（即使 num=1 也返回列表）。若 num 大于等于堆大小，则返回所有元素降序排列，不报错。

nsmallest(num, heap)：从堆中取出 num 个最小元素，按从小到大顺序返回列表。

这两个方法不仅适用于堆，也可直接用于普通列表，功能一致。

四、使用heapq合并两个有序列表

array_a = [10, 7, 15, 8]
array_b = [17, 3, 8, 20, 13]
array_merge = heapq.merge(sorted(array_a), sorted(array_b))
print("merge result:", list(array_merge))

运行结果：

merge result: [3, 7, 8, 8, 10, 13, 15, 17, 20]

merge(list1, list2)：将两个有序列表合并为一个新的有序迭代器。该方法可用于归并排序的实现。

五、heapq 替换数据的方法

array_c = [10, 7, 15, 8]
heapq.heapify(array_c)
print("before:", array_c)
# 先 push 再 pop
item = heapq.heappushpop(array_c, 5)
print("after: ", array_c)
print(item)
 
array_d = [10, 7, 15, 8]
heapq.heapify(array_d)
print("before:", array_d)
# 先 pop 再 push
item = heapq.heapreplace(array_d, 5)
print("after: ", array_d)
print(item)

运行结果：

before: [7, 8, 15, 10] after: [7, 8, 15, 10] 5 before: [7, 8, 15, 10] after: [5, 8, 15, 10] 7

heappushpop(heap, num)：先将 num 入堆，再弹出堆顶元素。 heapreplace(heap, num)：先弹出堆顶元素，再将 num 入堆。

两者均实现“入堆+出堆”操作，区别在于执行顺序。具体差异可参考代码示例。

到此这篇关于Python heapq库案例详解的文章就介绍到这了,更多相关Python heapq库内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！