CODEWITHSUNDEEP
pythonpython-2.7python-3.xheap
Alex
Alex

Reputation: 19124

How does heapq push comparison work in 2.7 vs 3.x

import heapq

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

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

This works in Python 2.7 but not in 3.x. As mentioned in the docs

In the future with Python 3, tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order.

How are non-comparable objects handled in 2.7's heapq.heappush?

Upvotes: 4

Views: 673

Answers (1)

Terry Jan Reedy
Terry Jan Reedy

Reputation: 19219

Let us assume that you want Foo instances to be compared by their ._x values. Your code may run in 2.x, but it will not work in any sensible fashion as Foo instancex will instead be compared by their ids. Python 3 protects you from such silent bugs by not having a useless default. heapq at least uses <. The following runs in 3.x and works correctly, at least for this example, in 2.x and 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)

Add other rich comparision methods as needed or desired. You could add if isinstance(other, Foo) else NotImplemented to the end of each return expression to make comparisons with non-Foo instances work better.

Upvotes: 2

Related Questions