heapq can't handle tuples having same priority if the item is not comparable

Question

>>> from heapq import heappush
>>> heap = []
>>> heappush(heap,(0,{"k":0}))
>>> heappush(heap,(0,{"k":1}))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'

This is mentioned in the official heapq document for python2 and python3 and the document suggests a DIY implementation of heapq to mitigate this problem.

Why is this happening? What is the underlying reason that such conflict is not resolved, giving that heapq is a really old library? Are there performance / other concerns for this? Why can't we just provide parameters like keep_old, keep_any as a feature to this library?

Brad Solomon · Accepted Answer · 2019-07-11T23:55:24.510

From the heapq docs section on Priority Queue Implementation Notes:

A solution to the first two challenges is to store entries as 3-element list including the priority, an entry count, and the task. The entry count serves as a tie-breaker so that two tasks with the same priority are returned in the order they were added.

A barebones interpretation of that:

from heapq import heappush
ecount = 0
heap = []

for priority, task in (
    (0, {"k":0}),
    (0, {"k":0}),
):
    heappush(heap, (priority, ecount, task))
    ecount += 1

Result:

>>> heap
[(0, 0, {'k': 0}), (0, 1, {'k': 0})]

(You can also do this with enumerate().)

To inject a bit of opinion into things:

Why is this happening? What is the underlying reason that such conflict is not resolved, giving that heapq is a really old library?

Not really sure, but the fact of the matter is that you can't logically compare two dict less than/greater than.

Independent of heapq, the comparison (0,{"k":0}) > (0,{"k":1}) will (rightfully so) raise TypeError. An emphasis of heapq is that operations should be deterministic: the tie-break should not be random, and it's up to you to situationally determine how to handle that.

Thanks. I was thinking that 3-tuple implementation is not available by default. Still pretty astonished that the implementation you supplied is not packaged as a default behavior (essentially `keep_new`). That error message is extremely misleading! — xxbidiao, Jul 11 '19 at 23:25

score 1 · Answer 2 · answered Jul 11 '19 at 23:12

1

My first thought is that heaps are required to be ordered; since you added two P0 items to the heap and the heap falls back to ordering the value when priorities are equal, the values must be ordered. if this is what you want, i'd subclass map as comparableMap("k", {"k":0}) and add a comparison method on that.

answered Jul 11 '19 at 23:12

Mr. Cat

55
3

That's a reasonable way too, if I had a custom class object. – xxbidiao Jul 11 '19 at 23:26

heapq can't handle tuples having same priority if the item is not comparable

2 Answers2