Python之实现一个优先级队列

问题

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

解决方案

下面的类利用 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))  #优先级为负数的目的是使得元素按照优先级从高到低排序
        # index 变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index 下标变量，可以确保元素按照它们插入的顺序排序
        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)

print(q.pop())
print(q.pop())
print(q.pop())

# Item('bar')
# Item('spam')
# Item('foo')
# 第一个 pop() 操作返回优先级最高的元素。 另外注意到如果两个有着相同优先级的元素（ foo 和 grok ），pop 操作按照它们被插入到队列的顺序返回的。

用heap创建堆

import heapq

nums=[1,2,3,4,5,6,7]
li=[]
for num in nums:
    heapq.heappush(li,num)
print(heapq.heappop(li) for _ in range(len(nums)))  #<generator object <genexpr> at 0x7fa0ff552938>
print(li)  # [1, 2, 3, 4, 5, 6, 7]