大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
优先级队列的实现
堆（heap）数据结构是一种优先队列。优先队列让你能够以任意顺序添加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min，这样做的效率要高得多。
使用heapq模块可以实现一个按优先级排序的队列，在这个队列上每次pop操作总是返回优先级最高的那个元素。
它包含6个函数，其中前4个与堆操作直接相关。必须使用列表来表示堆对象本身。
模块heapq中一些重要的函数。
|
函 数 |
描 述 |
|
heappush(heap, x) |
将x压入堆中 |
|
heappop(heap) |
从堆中弹出最小的元素 |
|
heapify(heap) |
让列表具备堆特征 |
|
heapreplace(heap, x) |
弹出最小的元素，并将x压入堆中 |
|
nlargest(n, iter) |
返回iter中n个最大的元素 |
|
nsmallest(n, iter) |
返回iter中n个最小的元素 |
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’)
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/190109.html原文链接：https://javaforall.net
