我有一个这样的堆(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
型
5条答案
按热度按时间muk1a3rh1#
如果您确实需要从
heap
中取出一个项目,但又想保留heap
,您可以延迟执行,并在项目自然出现时丢弃它,而不是在列表中搜索它。如果您将要删除的项目存储在黑名单
set
中,则每次heapq.heappop
检查该项目是否在set
中。如果存在,则丢弃它,然后再次heappop
,直到您获得未列入黑名单的项目,或者heap
为空alen0pnh2#
如果多个被删除的元素具有相同的值,那么黑名单集将是有问题的。相反,使用tombstone-counting-dict实现
heap_remove
:字符串
正如预期的那样,你已经摊销了O(1)的移除时间,并且只要你不在其他地方的堆上
popping
,堆的top
总是准确的。考虑这个数字列表,它们首先被全部推入堆,然后以相同的顺序“移除”(而不是弹出):
[三、三、二、七、一、四、二]
按预期工作:
型
但是移除是通过增加对象的tombstone来完成的。如果堆的顶部设置了tombstone,那么移除对象并递减tombstone计数器。
型
请注意,当第二个
heap_remove(3)
被调用时,@GP89的解决方案会崩溃,因为3
已经在tombstone集中。您可以探索此示例here。
j9per5c43#
有了以上两个想法,这里是一个完整的演示:我会尽快使它干净简洁。
字符串
ycl3bljg4#
在这种方法中,我基本上是在字典中跟踪元素。所以,无论何时,我删除它,搜索过程都变成了O(1)。
字符串
dwbf0jvd5#
恐怕只有heapq没有这样的方法。因为从堆中搜索元素需要
O(n)
。但是,您可以将它与
dict
之类的东西一起使用,这将为O(1)
提供搜索条目的时间。已删除:
我尝试使用字典记账,但我如何才能得到“创建测试”的索引时,它被插入?- Prakhar 3小时前
一种简单的方法是:
字符串
然后你可以通过访问这个
hdict
而不是你的O(n)
线性搜索来获得给定字符串的索引。