检查heapq是否包含valu

Question

我使用heapq对象来存储我实现的类的对象。

import heapq

heap = []
element1 = Element('A', 1)
element2 = Element('B', 2)
element3 = Element('C', 3)
heapq.heappush(heap, element1)
heapq.heappush(heap, element2)
heapq.heappush(heap, element3)

在我的类元素中，我覆盖方法__cmp__，以确保值是优先级

def __cmp__(self, other):
        return cmp(self.value, other.value)

现在我想写一个函数，它检查堆是否包含元素，这样 如果我想检查element = Element('A', 1)是否在堆中，答案将是True，如果我要检查element = Element('A',100)，答案也将是True，但是如果我想检查element = Element('D',1)，答案将是False。 如何实现这种方法？是否可以在不调用pop()方法的情况下检查heapq的元素？

Answer 1

在Element中添加方法__eq__，这样就可以使用关键字in检查成员身份（不使用__eq__，代码Element('A', 1) == Element('A', 1)将给出False）：

class Element:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __eq__(self, other):
        return self.key == other.key

堆只是python中的列表，因此只需使用以下命令，__eq__即可完成其余操作：

Element('A', 1) in heap

示例

import heapq

heap = []
element1 = Element('A', 1)
element2 = Element('B', 2)
element3 = Element('C', 3)
heapq.heappush(heap, element1)
heapq.heappush(heap, element2)
heapq.heappush(heap, element3)

print Element('A', 1) in heap      # True
print Element('A', 100) in heap    # True
print Element('D', 1) in heap      # False

Answer 2

solution by @enrico起作用，实现__eq__来检查元素是否在堆中，以及__cmp__来确定元素的优先级。然而，它会产生一些奇怪的副作用。例如，Element('A', 1)将同时是==到和<比Element('A', 2)。

或者，您可以只使用常规的tuples，而不是Element包装类。首先是数字，元组的自然顺序就足够堆了，为了检查堆中是否有某个元素，您可以通过zip项来获得实际键的列表（在您的示例中是字母）。

heap = []
heapq.heappush(heap, (1, 'A'))
heapq.heappush(heap, (3, 'C'))
heapq.heappush(heap, (2, 'B'))

print 'A' in zip(*heap)[1]
print 'D' in zip(*heap)[1]
while heap:
    print heapq.heappop(heap)

输出：

True
False
(1, 'A')
(2, 'B')
(3, 'C')