Python 中的优先级队列使用比较器

Question

有没有什么方法可以在Python?

我想让优先级高的节点排在队列前面

已编辑：例如：

class node:
  def __init__(self, label, priority):
      self.label = label
      self.priority = priority
  




node1 = node('a', 3)
node2 = node('b',2)
node3 = node('c', 1)
 
nodes in queue comes like this==> (node1,node2,node3)

Answer 1

您应该仔细阅读有关优先级队列的文档（python3 的 heapq）： https://docs.python.org/3/library/heapq.html#heapq.heapify

它指的是优先级队列，也有基于元组中的值排序的基本示例。

Answer 2

正如 Albin 所说，您需要使用 heapq 模块（除非您想从头开始编写自己的堆实现）。需要注意的一件非常重要的事情是，这个库只提供了最小堆的实现，而不是最大堆。

要为自定义对象编写比较器，您需要覆盖 __lt__ 函数（使用 < 运算符时调用的函数）。所以你的节点 class 看起来像这样：

class node:
  nodes = dict()

  def __init__(self, label, priority):
      self.label = label
      self.priority = priority
  
  def __lt__(self, other):
      # Note that we've reversed the operands here, since we want a max-heap.
      return other.priority < self.priority

然后，我们可以做一个堆如下：

import heapq

heap = []

node1 = node('a', 3)
node2 = node('b', 2)
node3 = node('c', 1)

heapq.heappush(heap, node1)
heapq.heappush(heap, node2)
heapq.heappush(heap, node3)

# Should print 'a', 'b', 'c' in that order.
for i in range(3):
    print(heapq.heappop(heap).label)

Python 中的优先级队列使用比较器

priority queue in Python using comparator

python

comparator

priority-queue