插入字典以堆Python

Question

我正在尝试使用（key，value）构建一个堆，所以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：不可排序的类型：dict（）<dict（）

什么是插入堆（number，dic）元素的正确方法？

谢谢。

Answer 1

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

元组不是一个很好的选择，因为可能会比较它们中的每个元素。例如，如果第一个元素（your 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)

将这些插入您的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个元组，并使用一个计数器作为第二个元素，以确保比较不会影响字典：

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

dictPython 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永远不需要比较 s 本身。