将字典插入堆中 Python

Question

我正在尝试构建一个包含（键，值）的堆，其中键是一个数字，而值是一个字典。

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: 无法进行比较的类型: dict() < dict()

插入到堆中的(数字，字典)元素的正确方法是什么？

谢谢。

- user1673206

---

好的，那你需要包含追踪信息和期望输出（并解释"crushes"的意思）。 - MSeifert

你确定你发布的示例会抛出那个异常吗？我看不出来这样比较字典，因为heap是空的。 - MSeifert

当运行此代码时，不会引发任何错误。 - Andria

请展示您的完整代码以便我们提供帮助。 - Andria

Answer 1

字典无法排序，因此您需要创建一个可以保留字典但不在比较中使用它的东西。

元组不是一个好选择，因为其中的每个元素可能被比较。例如，如果第一个元素（您的key）相等，则会比较第二个元素：

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

或者使用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)

把这些东西插入到你的堆中，这将保证字典不会被比较：

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

- MSeifert

---

使用类会更好，因为它更清晰。另一种解决方案将很难维护... - JenkinsY

Answer 2

Python 3 中无法比较 dict 实例：

>>> {'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 本身不需要进行比较。

- chepner

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

- Andria