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

大家好，又见面了，我是你们的朋友全栈君。

优先级队列的实现

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

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。