从O(logn)中的python heapq删除

发布时间：2020-12-20 12:21:24 所属栏目：Python 来源：网络整理

导读：我有一个像这样的堆( 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)中将具有项值的元组作为“create tests”删除并保留堆属性

我有一个像这样的堆( 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)中将具有项值的元组作为“create tests”删除并保留堆属性？

这是我能想到的(不是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)时间内搜索一个条目.

更新：

I tried using a dict for bookkeeping,but how can I get the index of “create test” when it was inserted? – Prakhar 3 hours ago

一个天真的方法是：

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!