目录/第 50 章 · heapq 模块
第 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] 建成堆并打印

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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] 建堆后弹两次,打印结果

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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 个

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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 个

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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 名

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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]

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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]))