Python学习记录05-实现一个优先级队列

huolong

发布于 2023-09-06 14:14:22

1440

发布于 2023-09-06 14:14:22

本节的内容是要实现一个优先级队列，并且当这个队列进行POP操作的时候，总是先弹出优先级最高的元素。今天我们就跟着文档一起学习一下。

文档使用了heapq模块来实现了一个优先级队列，我们由简到繁。来慢慢分析。这里先定义一个一会要按优先级排序的 Item。然后用它的2个对象进行比较，发现是会报错的。因为不支持比较。

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


if __name__ == '__main__':
    aa = Item('cat')
    bb = Item('dog')
    print( aa < bb)  #TypeError: '<' not supported between instances of 'Item' and 'Item'

我们非要给这个Item对象排序的话，可以用元组。

    aa = (5,Item('cat'))
    bb = (4,Item('cat'))
    print( aa > bb)   #输出为True

但是只用元组的第一个元素进行优先级比较的话，只适用于优先级不同的场景，如果优先级。如果优先级一样，则也会抛出 typeerror的异常。

bb = (4,Item('cat'))
    cc = (4,Item('fish'))
    print(bb < cc)  #TypeError: '<' not supported between instances of 'Item' and 'Item'

那为了避免这种场景，我们就需要在元组的第二个位置再引入一个元素inex，且让index的元素始终是不一样的，这样就优先级相同也不会报错，优先级不同index也不会有影响。！！Python 在做元组比较时候，如果前面的比较已经可以确定结果了，后面的比较操作就不会发生了

    bb = (4,0,Item('cat'))
    cc = (4,1,Item('fish'))
    print(bb

接下来我们看另一个例子,我在这里定义了一个堆，然后通过heapq的push方法往里添加元组元素，然后再输出heap 和pop。根据print那行可以得知，默认堆是从低优先级到高优先级排序的，pop每次是弹出最左边的元素。因为最左边的是最小的。这就是小顶堆。也就是小的元素在堆顶，每次把堆顶的弹出去，然后再维持堆的形状。

 heap = []
    heapq.heappush(heap,(1,'111'))
    heapq.heappush(heap,(0,'222'))
    heapq.heappush(heap,(3,'333'))
    heapq.heappush(heap,(2,'444'))
    print(heap)     #[(0, '222'), (1, '111'), (3, '333'), (2, '444')]
    print(heapq.heappop(heap)[-1])  #222
    # print(heapq.heappop(heap))  # [(0, '222')
    # print(heapq.heappop(heap))  # (1, '111')
    # print(heapq.heappop(heap))  #(2, '444')
    # print(heapq.heappop(heap))  #(3, '333')

我这里的需求是想每次pop，弹出最左边的元素，但是需要最左边的元素是最大的。这就需要我们在往里push 的时候，把优先级从高到低插入。也就是先插入优先级高的，在插入优先级低的，最后也就形成了大顶堆。所以这时候pop，弹出的就是最大的元素了。代码如下，只是需要把优先级改成负数即可。

 heap = []
    heapq.heappush(heap,(-1,'111'))
    heapq.heappush(heap,(0,'222'))
    heapq.heappush(heap,(-3,'333'))
    heapq.heappush(heap,(-2,'444'))
    print(heap)     # [(-3, '333'), (-2, '444'), (-1, '111'), (0, '222')]
    print(heapq.heappop(heap))  #(-3, '333')
    print(heapq.heappop(heap))  # (-2, '444')
    print(heapq.heappop(heap))  #(-1, '111')
    print(heapq.heappop(heap))  # (0, '222')

到这里我们有以下几个知识点

元组比较时候，如果优先级相同则会报错，所以需要添加第二元素 index
往堆里插入为了让最大堆元素最先弹出，所以优先级要反着来。
单独的Item不能比较

啰嗦了这么多，终于到了最后的用一个heapq来实现一个优先级队列，使得可以按照优先级，每次来pop出优先级最高的元素,完整代码如下

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)


if __name__ == '__main__':
    q = PriorityQueue()
    q.push(Item('dog'),1)
    q.push(Item('fish'),5)
    q.push(Item('cat'),3)
    q.push(Item('bird'),1)
    print(q.pop())  #Item('fish')
    print(q.pop()) #Item('cat')
    print(q.pop())  #Item('dog')
    print(q.pop())  #Item('bird')

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023年09月05日，如有侵权请联系 cloudcommunity@tencent.com 删除

python