python 优先级队列

简介

优先级队列是基于堆的，关于堆的时候可以参考文章堆，优先级队列就是入队时，会分配一个优先级，之后出队时，根据优先级出列。如，入队时：(4,'a'), (6,'r'), (3'd'),则出队顺序(6,'r'), (4,'a'),(3'd')。

优先级队列的python实现

class PriorityQueue(object):
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self._maxheap = MaxHeap(maxsize)

    def push(self, priority, value):
        # 注意这里把这个 tuple push 进去，python 比较 tuple 从第一个开始比较
        # 这样就很巧妙地实现了按照优先级排序
        entry = (priority, value)    # 入队的时候会根据 priority 维持堆的特性
        self._maxheap.add(entry)

    def pop(self, with_priority=False):
        entry = self._maxheap.extract()
        if with_priority:
            return entry
        else:
            return entry[1]

    def is_empty(self):
        return len(self._maxheap) == 0

def test_priority_queue():
    size = 5
    pq = PriorityQueue(size)
    pq.push(5, 'purple')    # priority, value
    pq.push(0, 'white')
    pq.push(3, 'orange')
    pq.push(1, 'black')

    res = []
    while not pq.is_empty():
        res.append(pq.pop())
    assert res == ['purple', 'orange', 'black', 'white']

test_priority_queue()

• 其中MaxHeap类是这节中堆实现过的
• 其实是根据堆的特性比较元组中第一个数字也就是优先级的大小。