从O（logn）中的python heapq中删除

Question

我有一个像这样的堆（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”的元组并保留heap属性？

这是我能想到的（不是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

Answer 1

如果您确实需要从heap中取出一个项，但希望保留heap，则可以懒洋洋地执行该操作，并在该项自然出现时将其丢弃，而不是在列表中搜索该项。

如果您将要删除的项目存储在黑名单set中，那么每次您heapq.heappop检查该项目是否在set中。如果它存在，则丢弃它并再次heappop，直到得到未列入黑名单的内容，或者heap为空

Answer 2

恐怕只有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)线性搜索来获取给定字符串的索引。

Answer 3

如果多个已删除的元素具有相同的值，则黑名单集将有问题。而是使用逻辑删除计数指令来实现heap_remove：

def heap_remove(heap, value):
  tombstones[value] = tombstones.get(value, 0) + 1
  while len(heap) and heap[0] in tombstones and tombstones[heap[0]]:
      heappop(heap)

正如预期的那样，您已经摊销了O（1）个删除时间，并且只要您不在堆的其他位置，堆的top总是准确的。

考虑一下这个数字列表，它们首先被推到堆中，然后按相同的顺序“移除”（而不是弹出）：

[3, 3, 2, 7, 1, 4, 2]

按预期插入工作：

After inserting 3 into heap, top = 3
After inserting 3 into heap, top = 3
After inserting 2 into heap, top = 2
After inserting 7 into heap, top = 2
After inserting 1 into heap, top = 1
After inserting 4 into heap, top = 1
After inserting 2 into heap, top = 1

但是删除是通过增加对象的墓碑来完成的。如果堆的顶部设置了墓碑，则移除对象并减少tomstone计数器。

Called remove( 3 )
  Marking 3 for deletion
Called remove( 3 )
  Marking 3 for deletion
Called remove( 2 )
  Marking 2 for deletion
Called remove( 7 )
  Marking 7 for deletion
Called remove( 1 )
  Marking 1 for deletion
  Deleting top 1
    Updated heap is: [2, 2, 3, 7, 3, 4]
  Deleting top 1
    Updated heap is: [2, 3, 3, 7, 4]
Called remove( 4 )
  Marking 4 for deletion
Called remove( 2 )
  Marking 2 for deletion
  Deleting top 2
    Updated heap is: [3, 3, 4, 7]
  Deleting top 3
    Updated heap is: [3, 7, 4]
  Deleting top 3
    Updated heap is: [4, 7]
  Deleting top 4
    Updated heap is: [7]
  Deleting top 7
    Updated heap is: []

注意，当第二个heap_remove(3)被称为@GP89的解决方案时，由于3已经在tombstone集合中而崩溃。

您可以研究这个示例here。