Python 堆 heapq

又见苍岚

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 安装下载与黑屏问题解决方案全局路径规划算法记录 2025 Python 版本性能测试 Flutter Hello World Flutter 安装环境配置 Ubuntu VMware 硬盘扩容后 SMBus Host controller not enabled 报错问题解决 Python NetworkX 教程 Docker GPU 报错 - Failed to initialize NVML Unknown Error 解决方案 Python matplotlib 图表绘制 cuda-toolkit 安装替代 Cuda 与 Cudnn Jinja2 Python 利用 docxtpl 和 Jinja2 生成基于模板的 Word 文档 Docker 实现 CPU 核心隔离 LoFTR 基于 Transformer 的特征提取匹配算法 OmniGlue 特征匹配 SuperGlue 使用图神经网络学习特征匹配 Ubuntu 下将 xlsx 文件按照 sheet 转换为图片 Python 使用 SQLAlchemy Python FastAPI 教程 openwrt 软路由配置安装 Nav2 地图文件（PGM/YAML）规范标准 3D OBJ 模型转换为 glb 瓦片格式 Python 源码 Redis 数据库介绍 Ubuntu 22.04 内核自动升级导致 MongoDB 7.0.12 错误记录 ubuntu 20.04 安装 ROS Noetic ubuntu 18.04 安装 ROS Melodic VMware Workstation Pro 个人免费版下载、安装、使用指南 Hybrid A-star 路径规划 Reeds-Shepp 曲线 Dubins 曲线 Linux kvm 虚拟机网络不通的问题解决方法 Ubuntu 自动内存清理 BiliBili 缓存视频转 mp4 Python 求解线性规划 3D Gaussian Splatting 官方源码实践记录 ImageMagick 教程 Ubuntu 22.04 安装 Colmap 对数几率 odds Ubuntu nmcli 网络管理工具使用指南 SuperPoint 自监督深度学习特征点提取 SyncTV Music Tag Web 在线音乐信息整理工具 ncm 格式转 mp3 MusicBrainz 音乐元数据百科数据库 Ubuntu 网络流量监控工具私人云音乐平台 Navidrome 入门手眼标定四元数（Quaternions） OHTTPS 实现免费自动 https 证书申请、更新、部署 ubuntu 22.04 安装 CloudCompare 单机 KVM 虚拟机冷迁移 Ubuntu 22.04 使用 mdadm 实现软 raid 小鱼一键安装 ROS-humble Fluid -46- 基于 Simpletex API 构建公式识别页面公式识别 API 简介 -- Simpletex 使用 Python web 部署库 waitress 3D Gaussian Splatting for Real-Time Radiance Field Rendering Ubuntu Swap 简介与空间扩展 Ubuntu 24.04 安装 forticlient Clash Verge 使用 MongoDB 7.0.17 集群 Docker 构建源码 Error code - 2013. Lost connection to MySQL server during query 问题解决 Python 日志记录库 loguru 使用指北 Python 实现 Web 日志查看服务 MySQL LOAD DATA LOCAL INFILE 极速数据加载 Image size exceeds limit of 89478485 pixels 解决方案 Docker 使用 NVIDIA GPU 驱动错误解决阿里云 docker 镜像仓库 Ubuntu中没有wired connected的解决方案 MinIO 简介 subconverter 代理订阅格式转换修复 node –openssl-legacy-provider is not allowed in NODE_OPTIONS 错误

Python 堆 heapq

Yiwei Zhang · 2023-08-12 · via 又见苍岚

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

简介

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

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

方法

heapify

1	`heapq.heapify(x)`

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

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)

import heapqa = [[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

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

import heapqa = [[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

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

import heapqa = [[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 元素进去

import heapqa = [[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

合并多个堆成一个

import heapqa = [[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 个元素

import heapqa = [[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 个最小元素

import heapqa = [[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阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

又见苍岚

简介

方法

heapify

heappush

heappop

heappushpop

heapreplace

merge

nlargest

nsmallest

建堆

参考资料