python中堆元素的比较顺序

Question

我使用堆来使用heapq生成一个优先级队列。在

我使用

heapq.heappush(h, (cost, node))

其中h是堆对象，cost是我对堆排序的项，node是自定义类的对象。在

当我运行代码时，当我用相同的cost在h中插入两个不同的项时，会出现以下错误

TypeError: unorderable types: SearchNode() < SearchNode()

其中SearchNode()是node的类

这个错误表明Python正在比较第二项。在

堆元素是否有比较顺序？如果是，如何解决算法中的关系，使其不会开始比较第二个项目。我想到的一个可能的解决方案是重载SearchNode()类的比较运算符。在

我对python很陌生，所以如果我遗漏了一些非常明显的东西，请随时指出。在

Answer 1

PQ with list和bisect，字符串作为存储对象。不需要更改存储对象。只需构造item = (cost, object)并将其插入PQ。在

import bisect
# PQ of items
PQ = [
    (10, 'aaa'),
    (30, 'cccc'),
    (40, 'dddd'),
]

def pq_insert(pq, item):
    keys = [e[0] for e in pq]
    i = bisect.bisect(keys, item[0])
    pq.insert(i, item)

e = (20, 'bbbb')
pq_insert(PQ, e)

一些REPL输出

^{pr2}$

Answer 2

引入一个不包括节点的小类：

class CostAndNode:
    def __init__(self, cost, node):
        self.cost = cost
        self.node = node

    # do not compare nodes
    def __lt__(self, other):
        return self.cost < other.cost

h = []

heapq.heappush(h, CostAndNode(1, node1))
heapq.heappush(h, CostAndNode(1, node2))

Answer 3

如果你能明智地决定一种比较节点的方法，你可以用它来打破联系。例如，可以为每个节点分配一个“标签”，您可以保证它是唯一的。你可以通过按字典顺序比较标签来打破联系

class SearchNode:
    def __init__(self, label):
        self.label = label
        #etc

    def __lt__(self, other):
        return self.label < other.label

这将确保(cost, node)的比较是确定的。在