cookbook 1.5

大马强

实现优先级队列

问题描述：
        希望给定一个可以设置优先级排序的序列，pop的顺序优先返回优先级最高的元素

借助heapq库实现

class priorityqueue():
    def __init__(self) -> None:
        self._queue = []
        self._index = 0

    def push(self, item, prority):
        heapq.heappush(self._queue, (-prority, self._index, item))  # -prority heapq中数值越小优先级越高，类似堆
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]


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

    def __repr__(self) -> str:
        return "Item({!r})".format(self.name)


q = priorityqueue()
q.push(Item("foo"), 1)
q.push(Item("coo"), 4)
q.push(Item("voo"), 5)
q.push(Item("boo"), 1)
q.push(Item("noo"), 3)

(-5, 2, Item('voo'))
(-4, 1, Item('coo'))
(-3, 4, Item('noo'))
(-1, 0, Item('foo'))
(-1, 3, Item('boo'))

• 比较的原理是相应下标依次对比，先比tuple[0] tuple[1]...., []和{}比较原理一样
• 同优先级按照其push顺序来排序
• 三元元组形式是为了进行方便的比较