I've been trying to add dictionaries to a list using the heappush function. The first heappush statement works fine, and the print statement after that is executed.
#random tests
node1 = {'a':1, 'b':2, 'c':3}
node2 = {'c':4, 'd':5, 'e':6}
lists = []
heappush(lists, node1)
print(lists)
heappush(lists, node2)
However, when I try to execute the second heappush statement, it gives me the following error.
[{'a': 1, 'b': 2, 'c': 3}]
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-24-c680e53f9699> in <module>()
5 heappush(lists, node1)
6 print(lists)
----> 7 heappush(lists, node2)
TypeError: '<' not supported between instances of 'dict' and 'dict'
Why is that? I know I can use append function to append dictionaries to the list, but I want to use heappush instead
CodePudding user response:
The heap
data structure stores the elements in the list in a specific format, so that the pop()
and push()
functions are both O(log n)
. When putting a new element in the heap
, we need to compare it with the other objects in the heap
to determine position of the new item in the list
, which is done using the comparison operators <
.
Python dicts don't have comparison operators defined to decide which dict is smaller/larger than the other. What is your use case for putting dicts
into a heap
? If you want to have some kind of sorted order with dicts you will need to define the comparator methods for the dict on your own.