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

本节的内容是要实现一个优先级队列,并且当这个队列进行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<cc)  #True  此时不报错了,因为有了,0,1 index来做比较了

接下来我们看另一个例子,我在这里定义了一个堆,然后通过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')

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

  1. 元组比较时候,如果优先级相同则会报错,所以需要添加第二元素 index
  2. 往堆里插入为了让最大堆元素最先弹出,所以优先级要反着来。
  3. 单独的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')
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇