2.7和3.x中heapq push比较是如何工作的？

Question

import heapq

class Foo(object):
    def __init__(self, x):
        self._x = x

l = [Foo(1)]
heapq.heapify(l)
heapq.heappush(l, Foo(2))

这在Python 2.7中有效，但在3.x中无效。如文档中所述：

在未来的Python 3中，如果优先级相等且任务没有默认比较顺序，则对于(优先级、任务)对元组比较将出现问题。

在2.7的heapq.heappush中如何处理不可比较对象？

- Alex

Answer 1

假设您希望通过它们的._x值来比较Foo实例。在2.x版本中，您的代码可能会“运行”，但是它不会以任何明智的方式“工作”，因为Foo实例将被比较其id而非其值。Python 3通过没有无用的默认值来防止这种静默错误。heapq至少使用<。以下代码在3.x中运行并正确工作，在2.x和3.x中的此示例中至少如此。

import heapq

class Foo(object):
    def __init__(self, x):
        self._x = x
    def __repr__(self):
        return 'Foo(%s)' % self._x
    def __lt__(self, other):
        return self._x < other._x

l = [Foo(1)]
heapq.heapify(l)
heapq.heappush(l, Foo(2))
print(l)

根据需要或者意愿添加其他的丰富的比较方法。你可以在每个return表达式的末尾添加if isinstance(other, Foo) else NotImplemented，以使与非Foo实例的比较更好地工作。

- Terry Jan Reedy

---

所以我理解...我想知道“2.7的heapq.heappush如何处理不可比较的对象？”这两个对象是否通过某些看似随机的方式进行比较（例如它们的哈希值）？还是当它们被添加到末尾时，它们只是不会筛选堆？或者还有其他什么情况？ - Alex

在2.x中，几乎所有对象都可以使用默认比较方式进行“比较”，我相信CPython的默认比较方式是按类名和id排序。其想法是，即使顺序是任意的，list.sort()应该始终起作用。当复数和Guido决定遵循数学约定时，这个规则被打破了，即复数不能在其自身之间排序，更不能与其他东西进行比较。 - Terry Jan Reedy

我刚刚尝试对一个包含两个相同类实例的列表进行堆化，但具有更高ID的实例被放在列表的开头。可能是其他原因，或者是ID的某些函数。 - Alex