问排序列表vs堆:删除列表中间的元素Python

EN

如果这些值可以用作dict键，那么可以很容易地同时使用堆和collections.Counter来跟踪每个值在概念上仍在集合中的数量。计数为0表示该值在概念上已被完全删除，尽管它可能仍存在于堆中。

下面是一个草图(未测试！)，其中c是collections.Counter的实例，h是用作heapq模块操作堆的列表：

要添加元素(expected case时间对数，以堆大小表示)：

heapq.heappush(h, elt)
c[elt] += 1

要删除元素(expected case常量时间)，请执行以下操作：

if not c[elt]:
    raise ValueError("element doesn't exist")
c[elt] -= 1
if not c[elt]:
    del c[elt]

要删除最小元素(从堆中弹出的每个概念上已经删除的项的预期大小写对数时间(在堆的缩小大小中))：

while True:
    if not h:
        raise ValueError("cannot find minimum in empty collection")
    elt = heapq.heappop(h)
    if c[elt]:
        c[elt] -= 1
        if not c[elt]:
            del c[elt]
        break
    # else the Counter believes it was deleted earlier

通过在堆旁边维护一个字典，可以避免不知道要删除的项的索引的问题。字典中的值与堆项目相同(可能是一个具有优先级值和对实际项目的引用的列表)。字典中的关键字与真实条目相同，因此很容易查找。

当您想要删除一个不是最小项的项时，您可以在字典中查找它并将其标记为已删除(可能是通过将对该项的引用设置为None)。不需要修改表示堆的列表，它具有对相同项的引用，因此它将看到该项已被删除，这是最低限度的删除。

也就是说，如果您经常执行“从数据中的任何位置删除项”操作，那么使用常规字典或集合可能会更好。您可以使用min在线性时间内获得最小值，而删除(任何项目，包括最小值)需要恒定的时间(平均摊销)。对于某些使用模式，这可能比处理堆更快。