插入字典以堆Python [英] Inserting dictionary to heap Python

问题描述

我正在尝试使用(键，值)构建堆，因此键是数字，而值是字典.

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)

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

The code crashes on heappush. The element probably not in the right format.

错误是:

TypeError:不可排序的类型:dict()< dict()

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

插入以堆积(number，dic)个元素的正确方法是什么?

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

谢谢.

推荐答案

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

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

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

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

或使用heap:

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

如果key被保证不相等，那么就不会有问题，因为不会比较第二个项目.

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

如果只想为dict提供一些存储空间，则可以简单地创建一个存储(key, value)的类，但只能比较key:

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)

将它们插入您的heap中，这将保证不会比较dict:

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

---

另一种选择是使用3个元组，并使用一个计数器作为第二个元素，以确保比较不会进入dict:

---

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

这篇关于插入字典以堆Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！