python - 在O(logn)中从python heapq删除

我有一个这样的堆(python，heapq模块)-

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))

如何在O(logn)中删除具有项值作为“创建测试”的元组并保留堆属性？

这就是我能想到的(不是O(logn))

for i in range(len(h)):
   if h[i][1] == "create tests":
      h[i], h[-1] = h[-1], h[i]
      popped = h.pop()
      heapq.heapify(h)
      break

最佳答案

恐怕仅使用heapq就没有这种方法。由于从堆中搜索元素需要O(n)。

但是，您可以将其与dict之类的东西一起使用，这给O(1)时间来搜索条目。

更新:



天真的方法是:

# remember to update this hdict when updating the heap.
hdict = { h[i][1]: i for i in range(len(h)) }

然后，您可以通过访问此hdict而不是O(n)线性搜索来获取给定字符串的索引。

关于python - 在O(logn)中从python heapq删除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13800947/