Insert a dictionary into a bunch

Question

I am trying to build a bunch with (key, value), so key is a number and value is a dictionary.

import heapq
heap = []
dic = {'val_1': 'number_1', 'val_2': 'number_2', 'val_3': 'number_3'}
insetToHeap = (2,dic)
heapq.heappush(heap, insetToHeap)

The code is broken into heappush. The item is probably not in the correct format.

EDIT:

error: TypeError: unorderable types: dict() < dict()

What is the correct way to insert into a bunch of elements (number, dic)?

Answer 1

Dictionaries cannot be ordered, so you need to create something that the dictionary can contain, but not use it in comparison.

Tuples are not a good choice, because each element of them can be compared. For example, if the first element (yours key) is equal, then the second element is compared:

>>> (1, {'a': 1}) < (1, {'a': 2})
TypeError: unorderable types: dict() < dict()

Or with heap:

>>> heap = []
>>> heapq.heappush(heap, (2, {'a': 1}))
>>> heapq.heappush(heap, (2, {'b': 2}))
TypeError: unorderable types: dict() < dict()

key , , .

dict, , (key, value), - key:

from functools import total_ordering

@total_ordering
class KeyDict(object):
    def __init__(self, key, dct):
        self.key = key
        self.dct = dct

    def __lt__(self, other):
        return self.key < other.key

    def __eq__(self, other):
        return self.key == other.key

    def __repr__(self):
        return '{0.__class__.__name__}(key={0.key}, dct={0.dct})'.format(self)

heap, , dict :

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, KeyDict(2, {'a': 1}))
>>> heapq.heappush(heap, KeyDict(2, {'b': 2}))
>>> heap
[KeyDict(key=2, dct={'a': 1}), KeyDict(key=2, dct={'b': 2})]

---

3 , , dict:

>>> from itertools import count
>>> cnt = count()
>>> heap = []
>>> heapq.heappush(heap, (2, next(cnt), {'a': 1}))
>>> heapq.heappush(heap, (2, next(cnt), {'b': 2}))
>>> heap
[(2, 0, {'a': 1}), (2, 1, {'b': 2})]

Answer 2

dict Python 3:

>>> {'a': 9} < {'a': 10}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'

, , :

>>> (2, {'a': 9}) < (3, {'a': 10})
True
>>> (2, {'a': 9}) < (2, {'a': 10})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'
>>>

, dict .

Answer 3

, , , , dict.

>>> heapq.heappush(heap, (0,dic))
>>> heapq.heappush(heap, (0,dic2))
Traceback (most recent call last):
  File "python", line 1, in <module>
TypeError: unorderable types: dict() < dict()

, , , - :

>>> heapq.heappush(heap, (0,dic))
>>> heapq.heappush(heap, (1,dic))
>>> show_tree(heap)

(0, {'val_1': 'number_1', 'val_2': 'number_2', 'val_3': 'number_3'})
(1, {'val_1': 'number_1', 'val_2': 'number_2', 'val_3': 'number_3'})
------------------------------------