位置: 编程技术 - 正文

Python实现优先级队列结构的方法详解(python优先级顺序)

编辑:rootadmin

推荐整理分享Python实现优先级队列结构的方法详解(python优先级顺序),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:python and or not优先级,优先级排序python,python中%的优先级,python and or not优先级,python and or not优先级,python and or not优先级,python中的优先级,python优先级运算符,内容如对您有帮助,希望把文章链接给更多的朋友!

最简单的实现一个队列至少满足2个方法,put和get.借助最小堆来实现.这里按"值越大优先级越高"的顺序.

使用heapq模块来实现下面的类利用 heapq 模块实现了一个简单的优先级队列:

下面是它的使用方式:

仔细观察可以发现,第一个 pop() 操作返回优先级最高的元素。 另外注意到如果两个有着相同优先级的元素( foo 和 grok ),pop操作按照它们被插入到队列的顺序返回的。

函数 heapq.heappush() 和 heapq.heappop() 分别在队列 _queue 上插入和删除第一个元素, 并且队列_queue保证第一个元素拥有最小优先级(1.4节已经讨论过这个问题)。 heappop() 函数总是返回”最小的”的元素,这就是保证队列pop操作返回正确元素的关键。 另外,由于push和pop操作时间复杂度为O(log N),其中N是堆的大小,因此就算是N很大的时候它们运行速度也依旧很快。

在上面代码中,队列包含了一个 (-priority, index, item) 的元组。 优先级为负数的目的是使得元素按照优先级从高到低排序。 这个跟普通的按优先级从低到高排序的堆排序恰巧相反。

index 变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index 下标变量,可以确保元素按照它们插入的顺序排序。 而且, index 变量也在相同优先级元素比较的时候起到重要作用。

为了阐明这些,先假定Item实例是不支持排序的:

如果你使用元组 (priority, item) ,只要两个元素的优先级不同就能比较。 但是如果两个元素优先级一样的话,那么比较操作就会跟之前一样出错:

Python实现优先级队列结构的方法详解(python优先级顺序)

通过引入另外的 index 变量组成三元组 (priority, index, item) ,就能很好的避免上面的错误, 因为不可能有两个元素有相同的 index 值。Python在做元组比较时候,如果前面的比较以及可以确定结果了, 后面的比较操作就不会发生了:

如果你想在多个线程中使用同一个队列,那么你需要增加适当的锁和信号量机制。 可以查看.3小节的例子演示是怎样做的。

深入思考函数 heapq.heappush() 和 heapq.heappop() 分别在队列 _queue 上插入和删除第一个元素, 并且队列_queue保证第一个元素拥有最小优先级(1.4节已经讨论过这个问题)。 heappop() 函数总是返回”最小的”的元素,这就是保证队列pop操作返回正确元素的关键。 另外,由于push和pop操作时间复杂度为O(log N),其中N是堆的大小,因此就算是N很大的时候它们运行速度也依旧很快。

在上面代码中,队列包含了一个 (-priority, index, item) 的元组。 优先级为负数的目的是使得元素按照优先级从高到低排序。 这个跟普通的按优先级从低到高排序的堆排序恰巧相反。

index 变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index 下标变量,可以确保元素按照它们插入的顺序排序。 而且, index 变量也在相同优先级元素比较的时候起到重要作用。

为了阐明这些,先假定Item实例是不支持排序的:

如果你使用元组 (priority, item) ,只要两个元素的优先级不同就能比较。 但是如果两个元素优先级一样的话,那么比较操作就会跟之前一样出错:

通过引入另外的 index 变量组成三元组 (priority, index, item) ,就能很好的避免上面的错误, 因为不可能有两个元素有相同的 index 值。Python在做元组比较时候,如果前面的比较以及可以确定结果了, 后面的比较操作就不会发生了:

如果你想在多个线程中使用同一个队列,那么你需要增加适当的锁和信号量机制。 可以查看.3小节的例子演示是怎样做的。

heapq 模块的官方文档有更详细的例子程序以及对于堆理论及其实现的详细说明。

详解Python中的__new__、__init__、__call__三个特殊方法 __new__:对象的创建,是一个静态方法,第一个参数是cls。(想想也是,不可能是self,对象还没创建,哪来的self)__init__:对象的初始化,是一个实例方法

实例解析Python中的__new__特殊方法 __new__方法是什么?如果将类比喻为工厂,那么__init__()方法则是该工厂的生产工人,__init__()方法接受的初始化参数则是生产所需原料,__init__()方法会按

Python的Django框架中使用SQLAlchemy操作数据库的教程 零、SQLAlchemy是什么?SQLAlchemy的官网上写着它的介绍文字:SQLAlchemyisthePythonSQLtoolkitandObjectRelationalMapperthatgivesapplicationdevelopersthefullpowerandflexibilityofSQL.SQLAlch

标签: python优先级顺序

本文链接地址:https://www.jiuchutong.com/biancheng/386940.html 转载请保留说明!

上一篇:KMP算法精解及其Python版的代码示例(kmp算法理解)

下一篇:详解Python中的__new__、__init__、__call__三个特殊方法(python:\n)

  • 进出口公司怎么做
  • 定期定额户申报表怎么填
  • 企业对伤残怎么赔偿?
  • 未收回的货款是企业资产吗
  • 广告公司属于服务企业吗
  • 增值税普通发票和普通发票的区别怎么交税
  • 企业稳岗补贴怎么查
  • 外资企业所得税和内资区别
  • 外聘人员需要扣个人所得税吗
  • 车辆保险代交车船使用税会计分录怎么写?
  • 销售无形资产增值税纳税义务发生时间
  • 消费税的纳税环节可能有
  • 营改增后利息收入交什么税
  • 劳保用品计入福利费嘛
  • 企业风险应对的基本类型包括
  • 个税申报时个人怎么填
  • 享受小型微利企业税收优惠的条件
  • 消费税的纳税义务人
  • 跨年的物业费如何记账
  • 银行承兑汇票的付款期限
  • 金税盘减免税款申报的时候怎么填写
  • rftray.exe - rftray是什么进程 有什么用
  • PHP:curl_share_init()的用法_cURL函数
  • 免抵退税务处理
  • php最好的编程语言
  • 车间耗材管理办法
  • 售后租回怎么理解
  • 短期借款利息计算
  • 固定资产与固定资产净值
  • 将预收款冲抵前欠货款会计分录
  • php 取字符串 前几位
  • 没有交过税怎么办
  • 预收账款发货
  • c语言中有哪些语句
  • 个人福利要交税吗
  • phpcms使用教程
  • 专用发票超过360天未认证
  • windows7的安装方式
  • 投资管理公司怎么收费
  • 废料处理没开票销项税
  • 公司无流水要交税不
  • 企业收到宣传费怎么做账
  • 研发费用的台账由谁做
  • 咨询费如何缴税
  • 取得投资款缴纳企业所得税吗
  • 担保费能否抵扣增值税
  • 上期留抵税额怎么在账上提现
  • 出口免税的税种包括
  • 出口退税勾选后电子税务局查不到发票
  • 事业单位职工福利费支出范围
  • 会计账簿的作用之一是编报和输出会计信息
  • Win7/Win8.1/Win10的UAC对话框“是”点不了的原因及解决方法
  • win2003回收站
  • winxp回收站在哪里
  • xp电脑怎么样
  • debian glibc
  • unix和linux是使用较为广泛的多用户交互
  • win8的计算器在哪里
  • windows10更新遇到错误怎么解决
  • windows 10预览版
  • 学习ExtJS fit布局使用说明
  • js实现计时器在线时间
  • 公认的经典
  • javascript模块化规范
  • flask完整项目实例
  • vue+axios登录
  • textview不换行
  • unity 2d ik
  • 百度地图给map添加
  • jquery设置图片大小
  • js判断用户输入密码
  • Optimizing Unity Games for Mobile Platforms
  • js清除文本框内的文字
  • javascript常用函数大全
  • python5.7汉诺塔
  • 西宁市房屋维修基金收费标准2021
  • 2022年中国烟草营收
  • 卷票发票丢失怎么办理
  • 进项税计提和上交会计分录
  • 房地产增值税怎么算举例说明
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设