惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

WordPress大学
WordPress大学
Stack Overflow Blog
Stack Overflow Blog
人人都是产品经理
人人都是产品经理
Y
Y Combinator Blog
钛媒体：引领未来商业与生活新知
钛媒体：引领未来商业与生活新知
D
DataBreaches.Net
GbyAI
GbyAI
Microsoft Security Blog
Microsoft Security Blog
博
博客园_首页
大猫的无限游戏
大猫的无限游戏
Jina AI
Jina AI
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
Engineering at Meta
Engineering at Meta
IT之家
IT之家
MongoDB | Blog
MongoDB | Blog
The GitHub Blog
The GitHub Blog
月光博客
月光博客
U
Unit 42
Hugging Face - Blog
Hugging Face - Blog
博
博客园 - 叶小钗
腾
腾讯CDC
B
Blog RSS Feed
博
博客园 - Franky
爱范儿
爱范儿

又见苍岚

COLMAP PatchMatch Stereo 算法详解 事件驱动的状态机框架：从理论到工程实践 Git 在国内网络环境下无法 Push 的排查与修复 —— 配置 Clash 代理 分段五次多项式插值原理详解 路径插值方法深度对比研究 Claude Code 使用指南 OpenClaw 记忆管理与技能创建指南 CBS(Conflict-Based Search)算法详解 A* 算法及其变种详解 OpenClaw 配置多 Agents Windows Powershell 无法加载文件，因为在此系统上禁止运行脚本问题的解决方案 MaxClaw 安装流程 大模型 AI 名词介绍 AList 网盘聚合工具简介 Protobuf 简介与测试 Claude Code 简介以及 GLM 4.7 模型接入 Github 歌词下载工具 163MusicLyrics Python __getattr__ 懒加载 Python TypedDict 机器人仿真平台 Gazebo 安装记录 机器人仿真平台 Gazebo 简介 多机器人路径规划问题(Multi-Agent Path Finding, MAPF)简介 Python exifread 读取修改过的 jpeg 信息错误问题修复 3D 坐标系变换的理解 3D 旋转矩阵基本概念 MongoDB Compass 介绍 Python 环境管理工具 uv Flutter 开发指南 Snipaste 安装下载与黑屏问题解决方案 全局路径规划算法记录
Python 堆 heapq
Yiwei Zhang · 2023-08-12 · via 又见苍岚

本文介绍堆和在Python内置库的实现。

简介

该模块提供了堆队列算法的实现，也称为优先级队列算法。

堆是二叉树，其中每个父节点的值小于或等于其任何子节点的值。

方法

heapify

1
heapq.heapify(x)

将列表 x 转换为线性时间内的就地堆。

1
2
3
4
5
6
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
-->
a
[[4, 'asdf'], [6, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf']]

heappush

压入新元素到堆 log(n)

1
2
3
4
5
6
7
8
9
import heapq
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
heapq.heappush(a, [1, 'etrfg'])
-->
a
[[1, 'etrfg'], [4, 'asdf'], [13, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf'], [7, 'asdf']]

heappop

从堆中弹出并返回最小的项，同时保持堆的不变性。

1
2
3
4
5
6
7
8
9
10
import heapq
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
heapq.heappush(a, [1, 'etrfg'])
b = heapq.heappop(a)
-->
b
[1, 'etrfg']

heappushpop

在堆上推送项，然后弹出并从堆中返回最小的项。

1
2
3
4
5
6
7
8
9
10
11
import heapq
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.heappushpop(a, [9, 'etrfg'])
-->
b
[4, 'asdf']
a
[[6, 'asdf'], [7, 'asdf'], [13, 'asdf'], [9, 'etrfg'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf']]

heapreplace

先 pop 堆顶元素，再push 元素进去

1
2
3
4
5
6
7
8
9
10
11
import heapq
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.heapreplace(a, [1, 'etrfg'])
-->
b
[4, 'asdf']
a
[[1, 'etrfg'], [6, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf']]

merge

合并多个堆成一个

1
2
3
4
5
6
7
8
9
import heapq
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.merge(a, a, a)
-->
list(b)
[[1, 'etrfg'], [1, 'etrfg'], [1, 'etrfg'], [6, 'asdf'], [6, 'asdf'], [6, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [13, 'asdf'], [7, 'asdf'], ...]

nlargest

返回最大的 n 个元素

1
2
3
4
5
6
7
8
import heapq
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.nlargest(3, a)
-->
[[67, 'asdf'], [45, 'asdf'], [22, 'asdf']]

nsmallest

返回 n 个最小元素

1
2
3
4
5
6
7
8
9
10
import heapq
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.nsmallest(3, a)
-->
b
[[4, 'asdf'], [6, 'asdf'], [13, 'asdf']]

建堆

元素需要自底向上方法建堆，底层堆建完后可以固定下来不需要根据上层堆的调整而进行调整。过程为从最后一个元素 index 向前，首先需要找到其父亲元素（index - 1) // 2 ，如果其前一个元素的父亲（index - 2) // 2是同一个节点（或者该元素是偶数下标，下标从0 开始），则他俩是兄弟，查找此三个元素中最小值，替换到父亲的位置，即完成了当前局部堆的构建，这样一路调整到数组起始位置，就完成了堆构建，时间复杂度 O(n)。

参考资料

文章链接：
https://www.zywvvd.com/notes/coding/python/python-heapq/python-heapq/

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。