第 50 章 / 70 · 高级 · 标准库深入
heapq 模块
堆:找最大最小、TopK
先介绍1 个 demo6 个任务答案可展开
一、本章介绍
heapq 提供堆操作:heapify 建堆、heappush 入堆、heappop 出堆(最小)、nlargest/nsmallest 找最大最小几个。
这一章从最小堆到 TopK 问题。
本章要点
- heapify 建堆
- heappush/heappop
- nlargest/nsmallest
- 堆是最小堆
二、先看 demo
下面这个例子把本章涉及的用法尽量全面地串了一遍,代码带逐行注释,可以直接复制到本地 .py 文件运行。
案例
先看一个完整例子
介绍 · 逐行注释import heapq
h=[3,1,5,2]
heapq.heapify(h)
print(h)
heapq.heappush(h,0)
print(heapq.heappop(h))
print(heapq.nsmallest(3,[5,2,8,1]))
print(heapq.nlargest(2,[5,2,8,1]))运行结果
[1, 2, 5, 3]
0
[1, 2, 5]
[8, 5]要点:heapq 是最小堆,heappop 弹出最小元素;nsmallest/nlargest 找最小/最大的 n 个,不需要完整排序。
三、6 个任务(自己先写,再看答案)
难度从入门到挑战逐步增加。每个任务的答案默认折叠,点开可看参考代码、运行结果;有第二种解法的也一并给出。代码都可以直接运行。
任务 1
建堆
自己写 · 附答案入门 ★☆☆解题提示:本题主要用到 heapify 建堆、heappush/heappop、nlargest/nsmallest。先对照要求自己写一遍,卡住了再展开答案。
用 heapify 把 [3,1,2] 建成堆并打印
参考答案(先自己写,再看)
参考答案一
import heapq
h=[3,1,2]; heapq.heapify(h); print(h)运行结果
[1, 3, 2]参考答案二(另一种解法)
import heapq
h=[]
for x in [3,1,2]: heapq.heappush(h,x)
print(h)任务 2
弹出最小
自己写 · 附答案入门 ★☆☆解题提示:本题主要用到 heapify 建堆、heappush/heappop、nlargest/nsmallest。先对照要求自己写一遍,卡住了再展开答案。
对 [3,1,2] 建堆后弹两次,打印结果
参考答案(先自己写,再看)
参考答案一
import heapq
h=[3,1,2]; heapq.heapify(h)
print(heapq.heappop(h),heapq.heappop(h))运行结果
1 2参考答案二(另一种解法)
print(*sorted([3,1,2])[:2])任务 3
找最小三个
自己写 · 附答案进阶 ★★☆解题提示:本题主要用到 heapify 建堆、heappush/heappop、nlargest/nsmallest。先对照要求自己写一遍,卡住了再展开答案。
用 nsmallest 找 [5,3,8,1,9] 最小的 3 个
参考答案(先自己写,再看)
参考答案一
import heapq
print(heapq.nsmallest(3,[5,3,8,1,9]))运行结果
[1, 3, 5]参考答案二(另一种解法)
print(sorted([5,3,8,1,9])[:3])任务 4
找最大两个
自己写 · 附答案进阶 ★★☆解题提示:本题主要用到 heapify 建堆、heappush/heappop、nlargest/nsmallest。先对照要求自己写一遍,卡住了再展开答案。
用 nlargest 找 [5,3,8,1,9] 最大的 2 个
参考答案(先自己写,再看)
参考答案一
import heapq
print(heapq.nlargest(2,[5,3,8,1,9]))运行结果
[9, 8]参考答案二(另一种解法)
print(sorted([5,3,8,1,9],reverse=True)[:2])任务 5
TopK 成绩
自己写 · 附答案挑战 ★★★解题提示:本题主要用到 heapify 建堆、heappush/heappop、nlargest/nsmallest。先对照要求自己写一遍,卡住了再展开答案。
找 [88,92,79,95,60] 的前 2 名
参考答案(先自己写,再看)
参考答案一
import heapq
print(heapq.nlargest(2,[88,92,79,95,60]))运行结果
[95, 92]参考答案二(另一种解法)
print(sorted([88,92,79,95,60],reverse=True)[:2])任务 6
合并有序
自己写 · 附答案挑战 ★★★解题提示:本题主要用到 heapify 建堆、heappush/heappop、nlargest/nsmallest。先对照要求自己写一遍,卡住了再展开答案。
用 merge 合并 [1,3,5] 和 [2,4,6]
参考答案(先自己写,再看)
参考答案一
import heapq
print(list(heapq.merge([1,3,5],[2,4,6])))运行结果
[1, 2, 3, 4, 5, 6]参考答案二(另一种解法)
print(sorted([1,3,5]+[2,4,6]))