我有一个像这样的堆（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
如果您确实需要从其中取出一个项目heap但又想保留它，heap您可以懒惰地做它并在项目自然出现时丢弃它，而不是在列表中搜索它。
如果您将要删除的项目存储在黑名单set中，则每次heapq.heappop检查该项目是否在set. 如果它存在，heappop请再次丢弃它，直到您得到未列入黑名单的内容，或者heap为空
如果多个删除的元素具有相同的值，则黑名单集会出现问题。而是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: []
请注意，当第二个heap_remove(3)被称为@GP89 的解决方案时，就像3在墓碑集中一样。
您可以在此处探索此示例。
有了以上两个想法，这里有一个完整的演示：我会尽快让它简洁明了。
from heapq import heappush, heappop
class Solution:
def demo():
deleted = {}
h = [0]
heappush(h, 789)
heappush(h, 101)
heappush(h, 101)
self.remove(h, 101, deleted)
max_val = self.peek(h, deleted)
def remove(self, h, y, deleted):
deleted[y] = deleted.get(y, 0) + 1
while len(h) > 0 and h[0] == y and deleted[y] > 0:
heappop(h)
deleted[y] -= 1
def peek(self, h, deleted):
while len(h) > 0 and deleted.get(h[0],0) > 0:
deleted[h[0]] -= 1
heappop(h)
return h[0]
在这种方法中，我基本上是在跟踪字典中的元素。所以，每当我删除它时，搜索过程就变成了 O(1)。
class RemoveHeap:
def __init__(self):
self.h = []
self.track = collections.defaultdict(collections.deque)
self.counter = itertools.count()
def insert_item(self, val):
count = next(self.counter)
item = [val, count, 'active']
self.track[val].append(item)
heapq.heappush(self.h, item)
def delete_item(self, val):
if val in self.track:
items = self.track[val]
for item in items:
if item[2] == 'active':
item[2] = 'deleted'
break
def pop_item(self):
while len(self.h) > 0:
item = heapq.heappop(self.h)
item_track = self.track[item[0]]
item_track.popleft()
if len(item_track) == 0:
del self.track[item[0]]
else:
self.track[item[0]] = item_track
if item[2] == 'active':
return item[0]
def peek_item(self):
item = self.h[0]
if item[2] == 'deleted':
x = self.pop_item()
self.insert_item(x)
return x
return item[0]
恐怕只有 heapq 没有这种方法。由于从堆中搜索元素需要O(n).
但是您可以将它与类似的东西一起使用dict，这O(1)为搜索条目提供了时间。
更新：
我尝试使用 dict 进行簿记，但是如何在插入“create test”时获取索引？– Prakhar 3 小时前
一种天真的方法是：
# remember to update this hdict when updating the heap.
hdict = { h[i][1]: i for i in range(len(h)) }
然后，您可以通过访问它hdict而不是O(n)线性搜索来获取给定字符串的索引。