从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"删除并保留堆属性？

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

如果多个删除的元素具有相同的值，则黑名单集将会出现问题。相反，heap_remove使用 tombstone-counting-dict 来实现：

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只要您不是popping来自其他地方的堆，您的堆的 总是准确的。

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

[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

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

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: []

请注意，当第二个被调用时，@GP89 ​​的解决方案会像逻辑删除集中已经存在的heap_remove(3)那样崩溃。3

您可以在此处探索此示例。

Answer 3

恐怕只有 heapq 没有这样的方法。由于从堆中搜索元素需要O(n).

\n\n

但您可以将它与类似的东西一起使用dict，这样可以有O(1)时间搜索条目。

\n\n

更新：

\n\n

\n

我尝试使用字典进行记账，但是如何在插入“create test”时获取它的索引？\xe2\x80\x93 普拉卡 3 小时前

\n

\n\n

一个天真的方法是：

\n\n

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

\n\n

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

\n