从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)中将具 我有一个像这样的堆( 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)线性搜索来获取给定字符串的索引.

总结

以上是内存溢出为你收集整理的从O(logn)中的python heapq删除全部内容，希望文章能够帮你解决从O(logn)中的python heapq删除所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。