Inserting dictionary to heap Python

Question

I'm trying to build a heap with (key, value) so the key is a number and the 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 crashes on heappush. The element probably not in the right format.

EDIT:

The error is:

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

What is the right way to insert to heap the (number, dic) elements?

Thanks.

Answer 1

Dictionaries can't be ordered, so you need to create something that can keep the dictionary but doesn't use it in comparisons.

Tuples are not a good choice because every element in them might be compared. For example if the first element (your key) is equal then the second item 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()

If the key is garantueed to be unequal then there's no problem because the second item won't be compared.

In case you just want some storage for the dict you could simply create a class that stores (key, value) but only ever compares the 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)

Insert these into your heap and this will garantuee that the dict won't be compared:

>>> 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})]

---

An alternative is to use 3 tuples using a counter as second element that garantuees the comparison won't go to the 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})]