heapq成员资格测试和替换

Question

例如来自官方heapq的示例：

>>> heap = []
>>> data = [(1, 'J'), (4, 'N'), (3, 'H'), (2, 'O')]
>>> for item in data:
...     heappush(heap, item)
...
>>> while heap:
...     print(heappop(heap)[1])
J
O
H
N

我想进一步实现一个有效的selective_push，这样

1. selective_push（（1，'M'））等效于heappush，因为'M'不在堆中
2. selective_push（（3.5，'N'））等效于heap [2] =（3.5，'N'）;从3.5 <4]开始为heapify（heap）
3. selective_push（（4.5，'N'））自4.5>起不执行任何操作4

以下实现说明了目标，但很慢：

def selective_push(heap,s):
   NotFound=True
   for i in range(len(heap)): #linear search
        if heap[i][1]==s[1]:
            if s[0]<heap[i][0]:
                 heap[i]=s      #replacement
                 heapify(heap)
            NotFound=False
            break
    if NotFound:
       heappush(heap,s)
我认为由于线性搜索速度很慢，这破坏了heapq.push的log（n）复杂度。替换率低，但是始终执行线性搜索。

例如，来自官方heapq的示例：>>> heap = [] >>> data = [（1，'J'），（4，'N'），（3，'H'），（2， 'O'）] >>>表示数据中的项目：... heappush（heap，item）... >>＆...

Answer 1

heapq docs有一个如何更改现有项目优先级的示例。 （该示例还使用heapq确保具有相同优先级的项目以添加时的相同顺序返回：由于您没有提到这是必需的条件，因此我通过删除该部分来简化了代码。 ）我还添加了您提到的与替换现有项目有关的逻辑。