CODEWITHSUNDEEP
pythonheapq
xxbidiao
xxbidiao

Reputation: 874

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

>>> 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?

Upvotes: 4

Views: 4539

Answers (2)

Brad Solomon
Brad Solomon

Reputation: 40878

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.

Upvotes: 6

Mr. Cat
Mr. Cat

Reputation: 55

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.

Upvotes: 1

Related Questions