Python cookbook(数据结构与算法)实现优先级队列的方法示例

本文实例讲述了Python实现优先级队列的方法。分享给大家供大家参考,具体如下:

问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素;

解决方案:采用heapq模块实现一个简单的优先级队列

# example.py
#
# Example of a priority queue
import heapq
class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index = 0
  def push(self, item, priority):
    heapq.heappush(self._queue, (-priority, self._index, item))
    self._index += 1
  def pop(self):
    return heapq.heappop(self._queue)[-1]
# Example use
class Item:
  def __init__(self, name):
    self.name = name
  def __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("Should be bar:", q.pop())
print("Should be spam:", q.pop())
print("Should be foo:", q.pop())
print("Should be grok:", q.pop())
Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
Should be bar: Item('bar')
Should be spam: Item('spam')
Should be foo: Item('foo')
Should be grok: Item('grok')
>>> 

可以看出:第一次执行pop()操作时返回的元素具有最高的优先级;对于相同优先级的两个元素(foo和gork)返回的顺序同它们插入到队列时的顺序相同。

在这段代码中,队列以元组(-priority, self._index, item)的形式组成,priority取负值是为了队列按照从高到低的顺序排列,这和堆默认的从小到大的排序相反。

变量index的作用是对相同优先级的元素以适当的顺序排列,特别对同优先级的元素间做比较操作时扮演了重要的角色。

Item实例无法进行次序比较:

a=Item('foo')
b=Item('bar')
print('a<b: ',a<b)
>>>
Traceback (most recent call last):
 File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py", line 27, in <module>
  print('a<b: ',a<b)
TypeError: unorderable types: Item() < Item()
>>>

如果以元组(priority,  item)的形式来表示元素,只要优先级不同,就可进行比较:

a=(1,Item('foo'))
b=(5,Item('bar'))
c=(1,Item('gork'))
print('a<b: ',a<b)
print('a<c: ',a<c)
>>>
a<b: True
Traceback (most recent call last):
 File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py", line 29, in <module>
  print('a<c: ',a<c)
TypeError: unorderable types: Item() < Item()
>>>

引入额外的索引值,以(priority, index, item)的方式建立元组,就可以避免相同优先级无法比较的问题,因为没有哪两个元组会有相同的index值;

a=(1,0,Item('foo'))
b=(5,1,Item('bar'))
c=(1,2,Item('gork'))
print('a<b: ',a<b)
print('a<c: ',a<c)
>>>
a<b: True
a<c: True
>>>

如果想将这个队列用于线程间通信,还需要增加适当的锁和信号机制。

(代码摘自《Python Cookbook》)

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

您可能感兴趣的文章:

  • Python数据结构与算法之字典树实现方法示例
  • Python cookbook(数据结构与算法)让字典保持有序的方法
  • Python cookbook(数据结构与算法)在字典中将键映射到多个值上的方法
  • Python 字典(Dictionary)操作详解
  • python两种遍历字典(dict)的方法比较
  • Python中字典创建、遍历、添加等实用操作技巧合集
  • Python中字典和JSON互转操作实例
  • Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例
  • Python cookbook(数据结构与算法)保存最后N个元素的方法
  • Python cookbook(数据结构与算法)从任意长度的可迭代对象中分解元素操作示例
  • Python cookbook(数据结构与算法)将序列分解为单独变量的方法
  • Python cookbook(数据结构与算法)字典相关计算问题示例
(0)

相关推荐

  • Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例

    本文实例讲述了python找到最大或最小的N个元素实现方法.分享给大家供大家参考,具体如下: 问题:想在某个集合中找出最大或最小的N个元素 解决方案:heapq模块中的nlargest()和nsmallest()两个函数正是我们需要的. >>> import heapq >>> nums=[1,8,2,23,7,-4,18,23,42,37,2] >>> print(heapq.nlargest(3,nums)) [42, 37, 23] >&g

  • python两种遍历字典(dict)的方法比较

    python以其优美的语法和方便的内置数据结构,赢得了不少程序员的亲睐.其中有个很有用的数据结构,就是字典(dict),使用非常简单.说到遍历一个dict结构,我想大多数人都会想到 for key in dictobj 的方法,确实这个方法在大多数情况下都是适用的.但是并不是完全安全,请看下面这个例子: 复制代码 代码如下: #这里初始化一个dict>>> d = {'a':1, 'b':0, 'c':1, 'd':0}#本意是遍历dict,发现元素的值是0的话,就删掉>>&

  • Python 字典(Dictionary)操作详解

    Python字典是另一种可变容器模型,且可存储任意类型对象,如字符串.数字.元组等其他容器模型.一.创建字典字典由键和对应值成对组成.字典也被称作关联数组或哈希表.基本语法如下: 复制代码 代码如下: dict = {'Alice': '2341', 'Beth': '9102', 'Cecil': '3258'} 也可如此创建字典: 复制代码 代码如下: dict1 = { 'abc': 456 };dict2 = { 'abc': 123, 98.6: 37 }; 注意:每个键与值用冒号隔开

  • Python cookbook(数据结构与算法)从任意长度的可迭代对象中分解元素操作示例

    本文实例讲述了python从任意长度的可迭代对象中分解元素操作.分享给大家供大家参考,具体如下: 从某个可迭代对象中分解出N个元素,但是可迭代对象的长度可能超过N,会出现"分解值过多"的异常: 使用"*表达式"来解决该问题: Python 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:43:06) [MSC v.1600 32 bit (Intel)] on win32 Type "copyright",

  • Python cookbook(数据结构与算法)将序列分解为单独变量的方法

    本文实例讲述了Python cookbook(数据结构与算法)将序列分解为单独变量的方法.分享给大家供大家参考,具体如下: 如果对象是可迭代的(任何序列),则可以进行分解操作,包括元组.列表.字符串.文件.迭代器以及生成器,可通过简单的一个赋值操作分解为单独的变量. 唯一要求:变量的总数和序列相吻合,否则将出错: Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 20:32:19) [MSC v.1500 32 bit (Intel)] on wi

  • Python cookbook(数据结构与算法)字典相关计算问题示例

    本文实例讲述了Python cookbook(数据结构与算法)字典相关计算问题.分享给大家供大家参考,具体如下: 问题:在字典上对数据执行各式各样的计算(比如求最小值.最大值.排序). 解决方案:利用zip()将字典的键-值对"反转"为值-键对序列. 例如:如下字典存放的股票名称和对应的价格: >>> prices = { 'ACME': 45.23, 'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.20, 'FB': 10.75 }

  • Python cookbook(数据结构与算法)在字典中将键映射到多个值上的方法

    本文实例讲述了Python在字典中将键映射到多个值上的方法.分享给大家供大家参考,具体如下: 问题:一个能将键(key)映射到多个值的字典(即所谓的一键多值字典[multidict]) 解决方案:如果想让键映射到多值,需要将这多个值保持到另一个容器如列表或集合中: >>> d={'a':[1,2,3],'b':[4,5]} >>> d {'b': [4, 5], 'a': [1, 2, 3]} >>> e={'a':{1,2,3,3},'b':{4,5

  • Python中字典创建、遍历、添加等实用操作技巧合集

    字段是Python是字典中唯一的键-值类型,是Python中非常重要的数据结构,因其用哈希的方式存储数据,其复杂度为O(1),速度非常快.下面列出字典的常用的用途. 一.字典中常见方法列表 复制代码 代码如下: #方法                                  #描述  -------------------------------------------------------------------------------------------------  D.c

  • Python中字典和JSON互转操作实例

    JSON是一种轻量级的数据交换格式,各种语言都有良好的支持.字典是Python的一种数据结构.可以看成关联数组. 有些时候我们需要设计到字典转换成JSON序列化到文件,或者从文件中读取JSON.简单备忘一下. Dict转JSON写入文件 复制代码 代码如下: #!/usr/bin/env python # coding=utf-8 import json d = {'first': 'One', 'second':2} json.dump(d, open('/tmp/result.txt', '

  • Python cookbook(数据结构与算法)保存最后N个元素的方法

    本文实例讲述了Python保存最后N个元素的方法.分享给大家供大家参考,具体如下: 问题:希望在迭代或是其他形式的处理过程中对最后几项记录做一个有限的历史记录统计 解决方案:选择collections.deque. 如下的代码对一系列文本行做简单的文本匹配操作,当发现有匹配时就输出当前的匹配行以及最后检查过的N行文本: from collections import deque def search(lines, pattern, history=5): previous_lines = deq

  • Python cookbook(数据结构与算法)让字典保持有序的方法

    本文实例讲述了Python让字典保持有序的方法.分享给大家供大家参考,具体如下: 问题:创建一个字典,同时对字典做迭代或序列化操作时,也能控制其中元素的顺序: 解决方案:可以使用collections模块中的OrderedDict类来控制字典中元素的顺序.当对字典做迭代时,他会严格按照元素初始添加的顺序进行.例如: from collections import OrderedDict d=OrderedDict() d['foo']=1 d['bar']=2 d['spam']=3 d['gr

  • Python数据结构与算法之字典树实现方法示例

    本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

随机推荐