如何在 Python 中实现优先级队列?

2022-01-21 00:00:00 python queue priority-queue heap

问题描述

很抱歉提出这么愚蠢的问题，但 Python 文档令人困惑......

Sorry for such a silly question but Python docs are confusing...

链接 1:队列实现http://docs.python.org/library/queue.html

它说 Queue 有一个优先级队列的类.但我找不到如何实现它.

It says that Queue has a class for the priority queue. But I could not find how to implement it.

class Queue.PriorityQueue(maxsize=0)

链接 2:堆实现http://docs.python.org/library/heapq.html

这里他们说我们可以使用 heapq 间接实现优先级队列

Here they say that we can implement priority queues indirectly using heapq

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue'

Python 中最有效的优先级队列实现是什么?以及如何实现?

Which is the most efficient priority queue implementation in Python? And how to implement it?

解决方案

Queue模块中的版本是使用heapq模块实现，因此它们对于底层堆操作具有相同的效率.

The version in the Queue module is implemented using the heapq module, so they have equal efficiency for the underlying heap operations.

也就是说，Queue 版本速度较慢，因为它添加了锁、封装和一个不错的面向对象的 API.

That said, the Queue version is slower because it adds locks, encapsulation, and a nice object oriented API.

heapq 文档中显示的优先队列建议旨在显示如何向优先级队列添加其他功能(例如排序稳定性和更改先前入队任务的优先级的能力).如果您不需要这些功能，那么基本的 heappush 和 heappop 功能将为您提供最快的性能.

The priority queue suggestions shown in the heapq docs are meant to show how to add additional capabilities to a priority queue (such as sort stability and the ability to change the priority of a previously enqueued task). If you don't need those capabilities, then the basic heappush and heappop functions will give you the fastest performance.

相关文章