优先级队列的实现_优先级队列rabbitmq

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

优先级队列的实现

堆（heap）数据结构是一种优先队列。优先队列让你能够以任意顺序添加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min，这样做的效率要高得多。

使用heapq模块可以实现一个按优先级排序的队列，在这个队列上每次pop操作总是返回优先级最高的那个元素。

它包含6个函数，其中前4个与堆操作直接相关。必须使用列表来表示堆对象本身。

模块heapq中一些重要的函数。                     

heappush()方法

函数heappush用于在堆中添加一个元素。请注意，不能将它用于普通列表，而只能用于使用各种堆函数创建的列表。原因是元素的顺序很重要（虽然元素的排列顺序看起来有点随意，并没有严格地排序）。
from heapq import * 
from random import shuffle 
data = list(range(10)) 
shuffle(data) 
heap = [] 
for n in data: 
   heappush(heap, n) 
print(heap)

heappush(heap, 0.5) 

print(heap)

运行结果： 
[0, 2, 1, 5, 3, 7, 4, 9, 8, 6]

[0, 0.5, 1, 5, 2, 7, 4, 9, 8, 6, 3]
元素的排列顺序并不像看起来那么随意。它们虽然不是严格排序的，但必须保证一点：位置i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i和2 * i + 1处的元素）。这是底层堆算法的基础，称为堆特征（heap property）。

heappop()方法

函数heappop弹出最小的元素（总是位于索引0处），并确保剩余元素中最小的那个位于索引0处（保持堆特征）。虽然弹出列表中第一个元素的效率通常不是很高，但这不是问题，因为heappop会在幕后做些巧妙的移位操作。
print(heappop(heap) )
0 
print(heappop(heap) )
0.5 
print(heappop(heap) )
1 
>>> heap 
[2, 5, 3, 6, 9, 8, 4, 7] 
 

heapify()方法

函数heapify通过执行尽可能少的移位操作将列表变成合法的堆（即具备堆特征）。如果你的堆并不是使用heappush创建的，应在使用heappush和heappop之前使用这个函数。
heap = [5, 8, 0, 3, 6, 7, 9, 1, 4, 2] 
heapify(heap) 
print(heap) 
[0, 1, 5, 3, 2, 7, 9, 8, 4, 6] 
 

heapreplace()方法

函数heapreplace用得没有其他函数那么多。它从堆中弹出最小的元素，再压入一个新元素。相比于依次执行函数heappop和heappush，这个函数的效率更高。
heapreplace(heap, 0.5) 
print(heap)
heapreplace(heap, 10) 
print(heap)
 

nlargest()和nsmallest()方法

nlargest(n, iter)和nsmallest(n, iter)，:分别用于找出可迭代对象iter中最大和最小的n个元素。这种任务也可通过先排序（如使用函数sorted）再切片来完成，但堆算法的速度更快，使用的内存更少（而且使用起来也更容易）。

import heapq

li1 = [6,7,9,4,3,5,8,10,1]
heapq.heapify(li1)
print(heapq.nlargest(3, li1))
print(heapq.nsmallest(3, li1))

输出结果

[10, 9, 8]

[1, 3, 4]

优先级队列的实现

import heapq

# priority 优先级

class PriorityQueue:

    def __init__(self):

        self._queue = []

        self._index = 0

    def push(self, item, priority):

        # heappush 在队列 _queue 上插入第一个元素

        heapq.heappush(self._queue, (-priority, self._index, item))

        self._index += 1

    def pop(self):

        # heappop 在队列 _queue 上删除第一个元素

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

class Item:

    def __init__(self, name):

        self.name = name

    def __repr__(self):

        return ‘Item({!r})’.format(self.name)

代码解读：

调用push（）方法，实现将列表转化为堆数据

插入的是元组，元组大小比较是从第一个元素开始，第一个相同，再对比第二个元素，我们这里采用的方案是如果优先级相同，那么就根据第二个元素，谁先插入堆中，谁的index就小，那么它的值就小

heapq.heappop() 方法得到，该方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素。

测试：

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’)