python如何实现优先级队列(附代码)

  • 更新时间:2022-09-06 09:39:58
  • 编辑:曹翰池
本篇文章给大家带来的内容是关于python如何实现优先级队列(附代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

1、需求

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

2、解决方案

利用heapq模块实现

代码:

import heapq

#利用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]

class Item:
    def __init__(self,name):
        self.name=name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    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())
    print(q.pop())
    #具有相同优先级的两个元素,返回的顺序同它们插入到队列时的顺序相同
    print(q.pop())
    print(q.pop())

运行结果:

Item('bar')
Item('spam')
Item('foo')
Item('grok')
上面的代码核心在于heapq模块的使用。函数heapq.heapqpush()以及heapq.heapqpop()分别实现将元素从列表_queue中插入和移除,且保证列表中第一个元素的优先级最低。heappop()方法总是返回【最小】的元素,因此这就是让队列能弹出正确元素的关键。此外,由于push和pop操作的复杂度都是O(logN),其中N代表堆中元素的数量,因此就算N的值很大,这些操作的效率也非常高。

上面代码中,队列以元组(-priority ,index,item)的形式组成。把priority取负值是为了让队列能够按照元素的优先级从高到底的顺序排列。

变量index的作用是为了将具有相同优先级的元素以适当的顺序排列。通过维护一个不断递增的索引,元素将以它们如队列时的顺序来排列。为了说明index的作用,看下面实例:

代码:

class Item:
    def __init__(self,name):
        self.name=name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    a=(1,Item('foo'))
    b=(5,Item('bar'))
    #下面一句打印True
    print(a<b)


    c=(1,Item('grok'))
    #下面一句会报错:TypeError: '<' not supported between instances of 'Item' and 'Item'
    print(c<a)


    d=(1,0,Item('foo'))
    e=(5,1,Item('bar'))
    f=(1,2,Item('grok'))
    #下面一句打印True
    print(d<e)
    #下面一句打印True
    print(d<f)

以上就是python如何实现优先级队列(附代码)的详细内容,更多请关注码农之家其它相关文章!

相关教程

  • Python爬取13个旅游城市数据的实操方法

    这篇文章主要介绍了Python 爬取13个旅游城市,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2019-11-23

  • python判断文件是否存在的方法

    python判断文件是否存在,可以使用os模块中的os.path.exists()方法用于检验文件;或者在程序中直接使用open()方法来检查文件是否存在和可读写;还可以使用pathlib模块检验文件是否存在。

    发布时间:2020-01-27

  • python数据封装json格式数据的实例方法

    本次内容是小编在网上整理的关于如何python数据封装json格式的内容总结,有兴趣的读者们参考下。

    发布时间:2019-08-30

  • Python OS模块实例用法

    这篇文章主要介绍了Python OS模块,结合实例形式总结分析了Python使用OS解析文件路径、判断文件、目录等相关操作技巧,需要的朋友可以参考下

    发布时间:2019-06-23

  • 2020版Python学习路线图(附学习资料)

    这篇文章主要介绍了Python学习路线图(2020最新版),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

    发布时间:2021-04-07

  • Python如何实现数据库连接

    介绍了如何进行数据库连接

    发布时间:2020-06-03

  • 27行Python代码批量将ppt转换为pdf

    这篇文章主要为大家详细介绍了批量将ppt转换为pdf的Python代码,只要27行,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2020-03-22

用户留言