开发者社区> 问答> 正文

实现一个优先级队列

怎样实现一个按优先级排序的队列? 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素

展开
收起
哦哦喔 2020-04-16 18:48:32 696 0
1 条回答
写回答
取消 提交回答
  • 下面的类利用 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)
    ...
    >>> q = PriorityQueue()
    >>> q.push(Item('foo'), 1)
    >>> q.push(Item('bar'), 5)
    >>> q.push(Item('spam'), 4)
    >>> q.push(Item('grok'), 1)
    >>> q.pop()
    Item('bar')
    >>> q.pop()
    Item('spam')
    >>> q.pop()
    Item('foo')
    >>> q.pop()
    Item('grok')
    >>>
    
    

    仔细观察可以发现,第一个 pop() 操作返回优先级最高的元素。 另外注意到如果两个有着相同优先级的元素( foo 和 grok ),pop 操作按照它们被插入到队列的顺序返回的。

    2020-04-16 18:49:01
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载