当前位置： 首页 > ds >正文

【Python】利用heapq 模块实现一个按优先级排序的队列

ds 2025/8/21 16:41:25

1 heapq 模块的堆排列

在 Python 的 heapq 模块中，元素是按照堆的性质排列的，具体来说，是按照二叉堆（binary heap）的性质。二叉堆是一种特殊的二叉树，它满足以下两个条件：

  1. 形状属性（Shape Property）：二叉堆是一棵完全二叉树，这意味着除了最后一层外，每一层都是满的，并且最后一层的节点尽可能地集中在左侧。

  2. 堆属性（Heap Property）：二叉堆分为最小堆（min-heap）和最大堆（max-heap）两种。

    • 最小堆：对于堆中的任意节点 i 及其子节点（2i+1 和 2i+2），节点 i 的值总是小于或等于其子节点的值。这意味着堆顶（即根节点）是所有元素中最小的。
    • 最大堆：对于堆中的任意节点 i 及其子节点（2i+1 和 2i+2），节点 i 的值总是大于或等于其子节点的值。这意味着堆顶是所有元素中最大的。

在 Python 的 heapq 模块中，默认实现的是最小堆。这意味着当你将元素添加到堆中时，它们会根据堆属性被重新排列，以确保堆顶元素是所有元素中最小的。这种排列方式允许 heapq.heappop 操作在对数时间内返回并移除最小元素。

1.1 堆的排列示例

假设我们有一个堆 [1, 2, 3, 4, 5]，它满足最小堆的性质：

    1/ \2   3/ \ / \
4  5 6  7

在这个堆中，每个父节点的值都小于或等于其子节点的值。例如，节点1的值小于其子节点2和3的值。

1.2 堆的操作

  • heapq.heappush(heap, item)：将一个新元素添加到堆中，并重新排列以保持堆的性质。
  • heapq.heappop(heap)：从堆中移除并返回最小元素（对于最小堆），然后重新排列以保持堆的性质。

通过这些操作，heapq 模块可以有效地实现优先级队列，其中元素的优先级由其在堆中的位置决定。

2 heapq.heappush(heap, item)

heapq.heappush 是 Python 标准库 heapq 模块中的一个函数，用于将元素添加到堆中。

函数原型

heapq.heappush(heap, item)

参数

  1. heap：一个列表，表示堆。在 Python 中，堆是通过列表实现的，列表的前几个元素（从索引0开始）构成堆的根节点。

  2. item：要添加到堆中的元素。

用法

heapq.heappush 函数将 item 添加到 heap 列表中，并重新调整列表以保持堆的性质。在最小堆中，父节点的值总是小于或等于其子节点的值，即heapq.heappush 函数是通过比较item的值来确定元素在最小堆中的排列， 函数的 item 参数可以是任何可比较的数据类型。Python 中的可比较数据类型包括但不限于整数、浮点数、字符串、元组以及任何实现了 __lt__（小于）方法的对象。

示例

import heapq# 创建一个空堆
heap = []# 向堆中添加元素
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)# 查看堆
print(heap)  # 输出: [1, 2, 3]

在这个例子中，我们创建了一个空堆，然后添加了三个元素。由于 heapq 实现的是最小堆，所以堆顶元素（索引0）是最小的元素。

注意事项

  • 堆的大小必须是2的幂次方减1，例如1, 3, 7, 15等。这是因为堆是通过二叉树实现的，每个父节点都有两个子节点（除了最后一层，可能只有一个子节点）。
  • 在实际应用中，堆通常用于实现优先级队列，其中元素的优先级由堆顶元素决定。

示例

在优先级队列中，我们通常需要根据元素的优先级来添加和移除元素。为了实现这一点，我们可以将元素和其优先级一起存储在堆中。例如：

import heapqclass PriorityQueue:def __init__(self):self._queue = []self._index = 0def push(self, item, priority):# 将元素和其优先级以及索引一起添加到堆中# 使用负优先级是因为 heapq 是最小堆，而我们通常希望优先级高的元素先出队heapq.heappush(self._queue, (-priority, self._index, item))self._index += 1def pop(self):# 移除并返回堆顶元素# 由于我们存储了负优先级，所以这里直接返回元组的最后一个元素return heapq.heappop(self._queue)[-1]# 使用示例
q = PriorityQueue()
q.push('task1', 3)
q.push('task2', 1)
q.push('task3', 2)print(q.pop())  # 输出: 'task1'
print(q.pop())  # 输出: 'task3'
print(q.pop())  # 输出: 'task2'

在这个例子中，我们创建了一个 PriorityQueue 类，它使用 heapq.heappush 来添加元素，并使用 heapq.heappop 来移除元素。元素的优先级由负值表示，因为 heapq 实现的是最小堆，而我们希望优先级高的元素先出队。

3 heapq.heappop(heap)

heapq.heappop 是 Python 标准库 heapq 模块中的一个函数，用于从堆中移除并返回堆顶元素。在 Python 的 heapq 模块中，堆是按照最小堆的方式组织的，即堆顶元素是所有元素中最小的。

函数原型

heapq.heappop(heap)

参数

  1. heap：一个列表，表示堆。这个列表必须已经按照堆的性质组织好，即满足最小堆的性质。

返回值

  • 返回堆顶元素，即最小元素。

用法

heapq.heappop 函数从 heap 列表中移除并返回堆顶元素，然后重新调整列表以保持堆的性质。在移除堆顶元素后，列表的最后一个元素会被移动到堆顶位置，然后通过堆调整操作（堆化）确保新的堆顶元素仍然是最小的。

示例

import heapq# 创建一个堆
heap = [3, 1, 2]# 确保列表是堆
heapq.heapify(heap)# 从堆中移除并返回堆顶元素
item = heapq.heappop(heap)
print(item)  # 输出: 1# 查看堆
print(heap)  # 输出: [2, 3]

在这个例子中，我们首先创建了一个列表 heap，然后使用 heapq.heapify 函数将其转换为一个堆。之后，我们使用 heapq.heappop 函数移除了堆顶元素（即最小元素），并打印了这个元素和剩余的堆。

注意事项

  • 使用 heapq.heappop 之前，确保列表已经是一个有效的堆。如果列表不是堆，那么 heapq.heappop 的行为将是未定义的。
  • 在实际应用中，heapq.heappop 通常用于实现优先级队列，其中元素的优先级由堆顶元素决定。

优先级队列中的使用

在优先级队列中，我们通常需要根据元素的优先级来移除元素。为了实现这一点，我们可以将元素和其优先级一起存储在堆中。例如：

import heapqclass PriorityQueue:def __init__(self):self._queue = []self._index = 0def push(self, item, priority):# 将元素和其优先级以及索引一起添加到堆中# 使用负优先级是因为 heapq 是最小堆，而我们通常希望优先级高的元素先出队heapq.heappush(self._queue, (-priority, self._index, item))self._index += 1def pop(self):# 移除并返回堆顶元素# 由于我们存储了负优先级，所以这里直接返回元组的最后一个元素return heapq.heappop(self._queue)[-1]# 使用示例
q = PriorityQueue()
q.push('task1', 3)
q.push('task2', 1)
q.push('task3', 2)print(q.pop())  # 输出: 'task2'
print(q.pop())  # 输出: 'task3'
print(q.pop())  # 输出: 'task1'

在这个例子中，我们创建了一个 PriorityQueue 类，它使用 heapq.heappush 来添加元素，并使用 heapq.heappop 来移除元素。元素的优先级由负值表示，因为 heapq 实现的是最小堆，而我们希望优先级高的元素先出队。每次调用 pop 方法时，都会从堆中移除并返回优先级最高的元素。

4 利用heapq 模块实现一个按优先级排序的队列

import heapqclass PriorityQueue:def __init__(self):self._queue = []self._index = 0def push(self, item, priority):# 将元素和其优先级以及索引一起添加到堆中# 使用负优先级是因为 heapq 是最小堆，而我们通常希望优先级高的元素先出队heapq.heappush(self._queue, (-priority, self._index, item))self._index += 1def pop(self):# 移除并返回堆顶元素# 由于我们存储了负优先级，所以这里直接返回元组的最后一个元素,[n]返回第n+1个元素，-1则返回最后一个元素return heapq.heappop(self._queue)[-1]

class Item:def __init__(self, name):self.name = namedef __repr__(self):# 返回对象的字符串表示形式，便于调试和输出return 'Item({!r})'.format(self.name)# 使用示例
q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)print(q.pop())  # 输出: Item('bar')
print(q.pop())  # 输出: Item('spam')
print(q.pop())  # 输出: Item('foo')
print(q.pop())  # 输出: Item('grok')

  1. 存储结构：

    • 在 push 方法中，元素被存储为一个元组 (-priority, self._index, item)。
    • heapq.heappush 将这个元组添加到堆中。
    • 例如，当调用 q.push(Item('foo'), 1) 时，存储的元组是 (-1, 0, Item('foo'))。

  2. 堆的性质：

    • heapq 是一个最小堆，它会根据元组的第一个元素（即 -priority）来排序。
    • 优先级高的元素（priority 值大）会被存储为更小的负值（-priority 值小），因此会排在堆的前面。

  3. pop 方法：

    • heapq.heappop 会移除并返回堆顶的元组。
    • pop 方法返回的是这个元组的最后一个元素，即 item。
    • 例如，当调用 q.pop() 时，返回的是元组 (-5, 1, Item('bar')) 的最后一个元素 Item('bar')。

  4. 输出结果：

    • 每次调用 q.pop()，都会返回堆顶元素的 item 部分。
    • 因此，输出的顺序是根据优先级从高到低（bar -> spam -> foo -> grok）。

假设我们按照代码中的顺序调用 push 和 pop 方法：

  1. 存储过程：

    • q.push(Item('foo'), 1)：存储 (-1, 0, Item('foo'))
    • q.push(Item('bar'), 5)：存储 (-5, 1, Item('bar'))
    • q.push(Item('spam'), 4)：存储 (-4, 2, Item('spam'))
    • q.push(Item('grok'), 1)：存储 (-1, 3, Item('grok'))

  2. 堆的结构：

    • 堆中的元素按照 -priority 排序，因此堆顶是 (-5, 1, Item('bar'))。

  3. pop 过程：

    • 第一次调用 q.pop()：返回 Item('bar')，堆中剩余 (-4, 2, Item('spam')) 和 (-1, 0, Item('foo'))、(-1, 3, Item('grok'))。
    • 第二次调用 q.pop()：返回 Item('spam')，堆中剩余 (-1, 0, Item('foo')) 和 (-1, 3, Item('grok'))。
    • 第三次调用 q.pop()：返回 Item('foo')，堆中剩余 (-1, 3, Item('grok'))。
    • 第四次调用 q.pop()：返回 Item('grok')，堆为空。

虽然堆中存储的是元组 (-priority, self._index, item)，但 pop 方法只返回元组的最后一个元素 item，因此输出中只看到 item。

http://www.xdnf.cn/news/18492.html

相关文章：

  • 数字化图书管理系统设计实践(java)
  • CorrectNav——基于VLM构建带“自我纠正飞轮”的VLN：通过「视觉输入和语言指令」预测导航动作，且从动作和感知层面生成自我修正数据
  • 学习嵌入式的第二十二天——数据结构——双向链表
  • 永磁同步电机谐波抑制算法（13）——传统预测控制与传统谐波抑制的碰撞
  • week2-[二维数组]排队
  • MySQL 50 道经典练习题及答案
  • Java毕业设计选题推荐 |基于SpringBoot+Vue的知识产权管理系统设计与实现
  • Effective C++ 条款52：写了placement new也要写placement delete
  • ES常用查询命令
  • SQL详细语法教程（七）核心优化
  • ubuntu系统上的conda虚拟环境导出方便下次安装
  • PiscCode使用MediaPipe Face Landmarker实现实时人脸特征点检测
  • YOLO11 到 C++ 落地全流程：ONNX 导出、NMS 判别与推理实战
  • Java 通过 m3u8 链接下载所有 ts 视频切片并合并转换为 mp4 格式
  • 《GPT-OSS 模型全解析：OpenAI 回归开源的 Mixture-of-Experts 之路》
  • 深入理解MySQL Ⅳ -- SQL性能分析工具
  • 文件操作NIO Files的简单使用
  • InfluxDB 查询性能优化实战（一）
  • SCAU学习笔记 - 自科三面前端方向实战演示
  • Disruptor核心接口EventHandler解析
  • 【Techlog】01入门-井筒数据整合软件的基本认识
  • C5.6:双电源发射极偏置、特殊类偏置、PNP型偏置电路
  • ODPS 十五周年实录 | 为 AI 而生的数据平台
  • 机器学习（Machine Learning, ML）
  • 项目1其二(验证码、jwt)
  • 《算法导论》第 33 章 - 计算几何学
  • 关于uniappx注意点1 - 鸿蒙app
  • 3ds Max 流体模拟终极指南：从创建到渲染，打造真实液体效果
  • 模拟tomcat接收GET、POST请求
  • 元宇宙的硬件设备：从 VR 头显到脑机接口