python 中堆元素的比较顺序

Question

我正在使用堆通过 heapq 创建优先级队列。

我使用

向队列中插入一个项目

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

其中 h 是堆对象，cost 是我用来订购堆的项目，node 是自定义 class 的对象。

当我运行代码时，当我在 h 中插入两个具有相同 cost

的不同项目时，出现以下错误

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

其中 SearchNode() 是 node

的 class

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

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

我是 python 的新手，所以如果我遗漏了一些非常明显的内容，请随时指出。

Answer 1

引入一个小的 class，比较中不包括节点：

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 2

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

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

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

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

Answer 3

PQ with list and bisect, strings as stored objects 例如。无需更改存储的对象。只需构建 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 输出

>>> print PQ
[(10, 'aaa'), (30, 'cccc'), (40, 'dddd')]
>>> e = (20, 'bbbb')
>>> pq_insert(PQ, e)
>>> print PQ
[(10, 'aaa'), (20, 'bbbb'), (30, 'cccc'), (40, 'dddd')]
>>>

python 中堆元素的比较顺序

Order of comparison for heap elements in python

python

sorting

algorithm

heap

python-3.x