<p>如果多个已删除的元素具有相同的值,则黑名单集将有问题。而是使用逻辑删除计数指令来实现<code>heap_remove</code>:</p>
<pre><code>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)
</code></pre>
<p>正如预期的那样,您已经摊销了O(1)个删除时间,并且只要您不在堆的其他位置,堆的<code>top</code>总是准确的。</p>
<p>考虑一下这个数字列表,它们首先被推到堆中,然后按相同的顺序“移除”(而不是弹出):</p>
<blockquote>
<p>[3, 3, 2, 7, 1, 4, 2]</p>
</blockquote>
<p>按预期插入工作:</p>
<pre><code>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
</code></pre>
<p>但是删除是通过增加对象的墓碑来完成的。如果堆的顶部设置了墓碑,则移除对象并减少tomstone计数器。</p>
<pre><code>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: []
</code></pre>
<p>注意,当第二个<code>heap_remove(3)</code>被称为@GP89的解决方案时,由于<code>3</code>已经在tombstone集合中而崩溃。</p>
<p>您可以研究这个示例<a href="https://repl.it/J12n/0" rel="nofollow noreferrer">here</a>。</p>