如何在Python中实现优先队列？

Question

非常抱歉问这样一个愚蠢的问题，但是Python文档让人感到困惑......

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

文档中说队列有一个优先级队列的类。但我找不到如何实现它。

class Queue.PriorityQueue(maxsize=0)

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

他们在这里说我们可以使用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中，哪种优先队列实现方式最有效？以及如何实现它？

- codersofthedark

---

可能是A generic priority queue for Python的重复问题。 - Ciro Santilli OurBigBook.com

Answer 1

在任何一种语言中，都不存在所谓的“最有效的优先队列实现”。

优先队列是关于权衡的。请参见http://en.wikipedia.org/wiki/Priority_queue

根据您计划如何使用它，应选择以下两个之一：

• O(log(N))插入时间和O(1)（findMin+deleteMin）*时间，或
• O(1)插入时间和O(log(N))（findMin+deleteMin）*时间

（*附注：大多数队列的findMin时间几乎总是O(1)，因此这里主要指如果插入时间为O(log(N))慢，则deleteMin时间可以快速达到O(1)，或者如果插入时间为O(1)快，则deleteMin时间必须慢达到O(log(N))。应注意，两者都可能像基于二叉树的优先队列一样不必要地缓慢。）

在后一种情况下，您可以选择使用Fibonacci堆实现优先队列: http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants（正如您所看到的，基本上是二叉树的heapq必须具有插入和findMin+deleteMin的O(log(N))）。

如果您正在处理具有特殊属性的数据（例如有界数据），则可以实现O(1)插入和O(1) findMin+deleteMin时间。只有对某些类型的数据才能这样做，否则您可能会滥用优先队列以违反O(N log(N))排序限制。 vEB树属于类似类别，因为您有一个最大集合大小（O(log(log(M)))不是指元素数量，而是指最大元素数量），因此您无法规避理论O(N log(N))通用比较排序限制。

实现任何语言中的队列，您只需要定义insert(value)和extractMin() -> value操作。这通常只涉及对底层堆的最小包装；请参阅http://en.wikipedia.org/wiki/Fibonacci_heap以实现自己的堆，或使用类似堆的现成库，如Pairing Heap（Google搜索显示http://svn.python.org/projects/sandbox/trunk/collections/pairing_heap.py）。

---

如果你只关心你引用的两种方法哪个更有效（你上面包含了http://docs.python.org/library/heapq.html#priority-queue-implementation-notes 的基于heapq的代码，与 Queue.PriorityQueue），那么：

网上似乎没有易于找到的讨论，说明Queue.PriorityQueue实际上在做什么；你需要深入源代码，它链接到帮助文档: http://hg.python.org/cpython/file/2.7/Lib/Queue.py。

   224     def _put(self, item, heappush=heapq.heappush):
   225         heappush(self.queue, item)
   226 
   227     def _get(self, heappop=heapq.heappop):
   228         return heappop(self.queue)

正如我们所看到的，Queue.PriorityQueue 也使用 heapq 作为底层机制。因此它们在渐近意义下同样糟糕。 Queue.PriorityQueue 可能允许并行查询，因此我敢打赌它可能会有非常轻微的常数倍开销。但是因为你知道底层实现（和渐近行为）必须相同，所以最简单的方法就是在同一个大数据集上运行它们。

（请注意，Queue.PriorityQueue 似乎没有删除条目的方法，而 heapq 则有。然而这是个双刃剑：好的优先级队列实现可能允许您在 O(1) 或 O(log(N)) 时间内删除元素，但如果您使用提到的 remove_task 函数，并让那些僵尸任务在队列中积累，因为您没有将它们从最小值中提取出来，那么您将看到渐近减速，否则您不会看到。当然，您首先无法对 Queue.PriorityQueue 进行此操作，因此这里不能进行比较。）

- ninjagecko

---

我对优先队列的理论相当了解，因此了解可能的数据结构。但问题是如何在Python中实现它，因为Python具有非常不同的数据结构集合。 - codersofthedark

谢谢@ninjagecko..你提出了一个很好的理论，人们必须知道才能决定正确的数据结构。-:) - codersofthedark

“deleteMin” 总是 O(log(N))。在你的第一句话中，如果你把它写成 “findMin+deleteMin”，似乎表明两者都可以是 O(1)，这可能会让人感到困惑。 - faraday

Answer 2

在队列模块中，版本是使用heapq模块实现的，因此它们具有相等的底层堆操作效率。话虽如此，队列版本较慢，因为它增加了锁、封装和一个良好的面向对象的API。 heapq文档中给出的优先级队列建议旨在展示如何向优先级队列添加附加功能（例如排序稳定性和更改之前排队任务的优先级）。如果您不需要这些功能，则基本的heappush和heappop函数将为您提供最快的性能。

- Raymond Hettinger

Answer 3

尽管这个问题已经被回答并标记为接受，但这里还是有一个简单的自定义优先队列实现，不使用任何模块来理解它的工作原理。

# class for Node with data and priority
class Node:

  def __init__(self, info, priority):
    self.info = info
    self.priority = priority

# class for Priority queue 
class PriorityQueue:

  def __init__(self):
    self.queue = list()
    # if you want you can set a maximum size for the queue

  def insert(self, node):
    # if queue is empty
    if self.size() == 0:
      # add the new node
      self.queue.append(node)
    else:
      # traverse the queue to find the right place for new node
      for x in range(0, self.size()):
        # if the priority of new node is greater
        if node.priority >= self.queue[x].priority:
          # if we have traversed the complete queue
          if x == (self.size()-1):
            # add new node at the end
            self.queue.insert(x+1, node)
          else:
            continue
        else:
          self.queue.insert(x, node)
          return True

  def delete(self):
    # remove the first node from the queue
    return self.queue.pop(0)

  def show(self):
    for x in self.queue:
      print str(x.info)+" - "+str(x.priority)

  def size(self):
    return len(self.queue)

在这里找到完整的代码和解释: https://www.studytonight.com/post/implementing-priority-queue-in-python（更新后的URL）

- iamabhishek

---

以下操作输出错误：pq.insert([8, 'item2']) pq.insert([10, 'item1']) pq.show() pq.insert([12, 'item3']) pq.insert([9, 'item4']) pq.show() - Saurabh