位置: 编程技术 - 正文
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) ，只要两个元素的优先级不同就能比较。 但是如果两个元素优先级一样的话，那么比较操作就会跟之前一样出错：
通过引入另外的 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)
