使用 Python 中的 Queue 和 Heapdict 模块实现优先级队列
pythonserver side programmingprogramming
优先级队列是一种抽象数据类型，类似于队列或堆栈，其中每个元素都附加有优先级。此处，优先级决定了元素从队列中出队的顺序，优先级较高的元素先于优先级较低的元素出队。
优先级队列将使用不同的数据结构来实现，例如堆、数组或平衡树。最常用的实现是堆，它是基于二叉树的数据结构，每个节点的值都大于或等于子节点的值。
优先级队列的类型
优先级队列主要有两种类型:最小优先级队列和最大优先级队列。在最小优先级队列中，优先级较低的元素将首先出队，而在最大优先级队列中，优先级较高的元素将首先出队。优先级队列广泛应用于任务调度、网络路由、作业优先级划分和霍夫曼编码等应用中。
使用 heapdict 模块的优先级队列
在 Python 中，我们有 heapq、queue 和 heapdict 模块。在本文中，让我们看看如何使用队列和 heapdict 模块实现优先级队列。在 heapdict 模块中，我们有 push 和 pop 方法，用于根据优先级将项目添加到队列中以及从队列中删除项目。
push 方法将项目和优先级作为输入参数，并将项目添加到优先级队列和 heapdict 中。 pop 方法删除项目并返回已删除的项目以及已删除的项目和堆字典中项目的优先级。
示例
在此示例中，我们将创建名为 PriorityQueueWithHeapdict 的类，并使用函数 push 根据给定的优先级将项目添加到队列中。此函数将项目和项目的优先级作为输入参数。接下来，我们将使用定义的类和函数将项目添加到优先级队列中。
from query import PriorityQueue
from heapdict import heapdict
class PriorityQueueWithHeapdict:
def __init__(self):
self._queue = PriorityQueue()
self._heapdict = heapdict()
def push(self, item, priority):
self._queue.put(priority)
self._heapdict[priority] = item
q = PriorityQueueWithHeapdict()
q.push('task 1', 3)
q.push('task 2', 1)
q.push('task 3', 2)
print("根据优先级将项目添加到优先级队列和 heapdict")
输出
根据优先级将项目添加到优先级队列和 heapdict
示例
在前面的示例中，我们创建了带有 push 函数的类，现在我们将在同一个类中创建 pop 函数。pop 函数用于删除具有最高优先级的项目，并删除 heapdict 中的项目。
from queue import PriorityQueue
from heapdict import heapdict
class PriorityQueueWithHeapdict:
def __init__(self):
self._queue = PriorityQueue()
self._heapdict = heapdict()
def push(self, item, priority):
self._queue.put(priority)
self._heapdict[priority] = item
def pop(self):
priority = self._queue.get()
item = self._heapdict[priority]
del self._heapdict[priority]
return item
def is_empty(self):
return self._queue.empty()
q = PriorityQueueWithHeapdict()
q.push('task 1', 3)
q.push('task 2', 1)
q.push('task 3', 2)
while not q.is_empty():
print(q.pop())
输出
task 2 task 3 task 1
