[python]如何实现一个优先级队列

模块

heapq

代码

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]


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

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


def 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())

if __name__ == '__main__':
    main()

第一个 pop()操作返回优先级最高的元素。 另外注意到如果两个有 着相同优先级的元素( foogrok ),pop操作按照它们被插入到队列的顺序返回的

Pycharm追踪

加入断点

push操作

pop操作

执行结果

结论

  1. 函数 heapq.heappush()heapq.heappop() 分别在队列 _queue 上插入和删除第一个元素
  2. heappop()总是返回最小的元素,这是保证队列pop操作返回正确元素的关键
  3. pushpop的时间复杂度为O(N),所以就算N很大,运行速度也很快
  4. (-priority, index, item),优先级为负数的原因就是使得元素按照优先级从高到低排序
  5. index变量的作用是保证同等优先级元素的正确排序,其实就是插入顺序

注:本文使用的实例代码,参考自《python cookbook 第三版》

剑气纵横三万里

“为什么要努力?” “想去的地方很远,想要的东西很贵,喜欢的人很优秀,父母的白发,朋友的约定,周围人的嘲笑,以及,天生傲骨。”

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

相关推荐

暂无内容!