位置: 编程技术 - 正文

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)

  • 营业执照注销要收费用吗
  • 技术开发免征增值税吗
  • 已认证的进项税发票要退回,怎么操作
  • 企业股权转让如何避税收
  • 公司为员工租房费用的会计分录
  • 公司成立筹备工作小组主要任务是什么
  • 非正常损失进项税额转出计算公式
  • 收到国债本金和利息会计分录
  • 银行结算方式包括哪些内容
  • 收购烟叶委托加工烟丝组成计税价格
  • 增值税专票需要哪些开票信息
  • 人工成本如何分摊到服务成本
  • 小规模免征增值税政策
  • 残疾人就业保障金
  • 工会经费具体用途是什么
  • 待处理流动资产损失属于什么科目
  • 进口原木的增值税率
  • 基金赎回未到账可继续买吗?
  • 农副产品免税怎么报税
  • 不应该计入管理费用的
  • 公司是否有审计资质
  • 租车费增值税专用发票
  • 上一年度多交年度所得税可以退税吗
  • 委托贷款利息收入增值税
  • 增值税专用发票丢了怎么补救
  • 长期股权投资的账务处理
  • 小规模纳税人确认收入时要确认税吗
  • 无法使用内置管理员账户打开Edge
  • AUTOMATIC1111/stable-diffusion-webui安装教程
  • 非货币性资产交换以公允价值为基础进行计量
  • 栅格布局实现
  • 合伙人资本属于股东吗
  • 公司开发新产品或购买许可证最快的方法是
  • php pdo连接sqlserver
  • 本月认证上月的进项票如何做
  • 长期待摊费用应该怎么摊销
  • 2018年残保金申报表填表说明
  • 公司变更需要哪些资料~问华杰 财务
  • gpu版本的pytorch
  • css面试题及答案
  • numpy的简单例子
  • php授权ip访问
  • groupinfo命令
  • mysql事件使用方法
  • python里%s
  • 用税盘开发票税费扣除是怎么回事?
  • 织梦内容页模板修改
  • 工资只计提没有发放需要申报个税吗
  • 净营业周期为负数
  • 技术服务合同的税率
  • 收据十万大写金额填写样本
  • 销售折扣购物卡对公司财务的好处
  • 租赁厂房对方不租怎么办
  • 坏账核算备抵法的优缺点
  • 进项留底是什么科目
  • 税务局多扣的税可以退吗
  • 试驾车折旧残值怎么计算
  • 变更印鉴单位公函格式
  • 期初借款余额计算公式
  • 《实施条例》第二十七条
  • 小规模增值税减免申报表怎么填
  • 汽车价外费用
  • 其他业务收入如何开票
  • 体检费用开发票给公司怎么开
  • 小规模纳税人购进税控收款机
  • 固定资产转固流程图
  • sqlserver备份数据库命令
  • mysql 数据修改
  • xp系统注册表空白怎么办
  • mac怎样修改用户名
  • icg是什么文件
  • win7怎么设置u盘启动为第一启动项
  • ,linux
  • shell if -lt
  • AndroidManifest.xml文件属性详解
  • 北京增值税普通发票图片
  • 年轻干部是什么意思
  • 社会福利企业可以投资吗
  • 税务实名认证如何操作
  • 三免三减半政策文件
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设