有没有办法检查 Python 中的优先级队列中是否存在优先级?
Is there a way to check if a priority exists in a priority queue in Python?
我对 Python 比较陌生。我正在尝试使用 queue.PriorityQueue()
class
并有一个问题。有没有办法检查是否存在特定优先级?
例如,我有以下 (priority, element)
:
(0,A), (1,B), (2,C), (2,D)
有什么方法可以检查优先级 2
是否存在? (是的,因为 C
和 D
都是 2。)
我可以获得特定优先级的元素吗?所以,如果我想要优先级为 2
的元素,它会给我 C
和 D
?
我在优先队列上看到的唯一官方文档是:Priority Queue official documentation
关于此 class 是否有任何其他文档?喜欢我可以使用的方法吗? class/ 可用字段的结构?
我的理解是,您的最终目标是将具有相同优先级的任务放在一个列表中并一起返回。所以:
如果您查看 queue.PriorityQueue
的代码(我看过),您会发现它基于 [=15] 的 heappush
和 heappop
方法=]模块,实现了堆队列算法。参见 heapq。如果您进一步查看此页面,他们甚至会展示如何使用 heapq 来实现优先级队列。这个实现比您需要的要复杂一些,因为它支持更改已添加任务的优先级的能力,并且它不能完全按照您的意愿处理具有相同优先级的多个任务。但这些更改很容易实现:
from heapq import heappush, heappop
class PriorityQueue:
def __init__(self):
self._pq = [] # list of entries arranged in a heap
self._priority_finder = {} # mapping of priority to entries
def add_task(self, task, priority=0):
'Add a new task'
# any tasks with this priority?
entry = self._priority_finder.get(priority)
if entry:
entry[1].append(task)
else:
entry = [priority, [task]]
self._priority_finder[priority] = entry
heappush(self._pq, entry)
def pop_task(self):
'Remove and return the lowest priority tasks. Raise KeyError if empty.'
if not self._pq:
raise KeyError('pop from an empty priority queue')
priority, tasks = heappop(self._pq)
del self._priority_finder[priority]
return priority, tasks
def __bool__(self):
'return True if any tasks on the queue'
return True if self._pq else False
pq = PriorityQueue()
pq.add_task('a', 4) # task 'a' with priority 4
pq.add_task('b', 2)
pq.add_task('c', 4)
pq.add_task('d', 2)
pq.add_task('e', 1)
while pq:
print(pq.pop_task())
打印:
(1, ['e'])
(2, ['b', 'd'])
(4, ['a', 'c'])
我对 Python 比较陌生。我正在尝试使用 queue.PriorityQueue()
class
并有一个问题。有没有办法检查是否存在特定优先级?
例如,我有以下 (priority, element)
:
(0,A), (1,B), (2,C), (2,D)
有什么方法可以检查优先级 2
是否存在? (是的,因为 C
和 D
都是 2。)
我可以获得特定优先级的元素吗?所以,如果我想要优先级为 2
的元素,它会给我 C
和 D
?
我在优先队列上看到的唯一官方文档是:Priority Queue official documentation
关于此 class 是否有任何其他文档?喜欢我可以使用的方法吗? class/ 可用字段的结构?
我的理解是,您的最终目标是将具有相同优先级的任务放在一个列表中并一起返回。所以:
如果您查看 queue.PriorityQueue
的代码(我看过),您会发现它基于 [=15] 的 heappush
和 heappop
方法=]模块,实现了堆队列算法。参见 heapq。如果您进一步查看此页面,他们甚至会展示如何使用 heapq 来实现优先级队列。这个实现比您需要的要复杂一些,因为它支持更改已添加任务的优先级的能力,并且它不能完全按照您的意愿处理具有相同优先级的多个任务。但这些更改很容易实现:
from heapq import heappush, heappop
class PriorityQueue:
def __init__(self):
self._pq = [] # list of entries arranged in a heap
self._priority_finder = {} # mapping of priority to entries
def add_task(self, task, priority=0):
'Add a new task'
# any tasks with this priority?
entry = self._priority_finder.get(priority)
if entry:
entry[1].append(task)
else:
entry = [priority, [task]]
self._priority_finder[priority] = entry
heappush(self._pq, entry)
def pop_task(self):
'Remove and return the lowest priority tasks. Raise KeyError if empty.'
if not self._pq:
raise KeyError('pop from an empty priority queue')
priority, tasks = heappop(self._pq)
del self._priority_finder[priority]
return priority, tasks
def __bool__(self):
'return True if any tasks on the queue'
return True if self._pq else False
pq = PriorityQueue()
pq.add_task('a', 4) # task 'a' with priority 4
pq.add_task('b', 2)
pq.add_task('c', 4)
pq.add_task('d', 2)
pq.add_task('e', 1)
while pq:
print(pq.pop_task())
打印:
(1, ['e'])
(2, ['b', 'd'])
(4, ['a', 'c'])