python - 将字典插入堆Python

Question

我正在尝试使用 (key, value) 构建一个堆，因此键是一个数字，值是一个字典。

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

代码在 heappush 上崩溃。该元素的格式可能不正确。

编辑:

错误是:

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

将(number, dic) 元素插入到堆中的正确方法是什么？

谢谢。

Answer 1

字典不能排序，所以你需要创建一些可以保留字典但不用于比较的东西。

元组不是一个好的选择，因为它们中的每个元素都可能被比较。例如，如果第一个元素(您的 key)相等，则比较第二个元素:

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

或者使用堆:

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

将这些插入到您的堆中，这将保证不会比较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 个元组，使用一个计数器作为第二个元素，保证比较不会进入字典:

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