Python:从堆中删除元素

发布于 2021-01-29 15:09:33

Python具有heapq实现堆数据结构的模块,并且它支持一些基本操作(推送,弹出)。

如何从O(log n)中的堆中删除第i个元素?甚至可以使用heapq还是必须使用另一个模块?

请注意,文档底部有一个示例:http :
//docs.python.org/library/heapq.html
,它建议了一种可能的方法-这不是我想要的。我希望删除元素,而不仅仅是标记为已删除。

关注者
0
被浏览
71
1 个回答
  • 面试哥
    面试哥 2021-01-29
    为面试而生,有面试问题,就找面试哥。

    您可以很容易地从堆中删除第i个元素:

    h[i] = h[-1]
    h.pop()
    heapq.heapify(h)
    

    只需将要删除的元素替换为最后一个元素,然后删除最后一个元素,然后重新堆化堆即可。这是O(n),如果需要,您可以在O(log(n))中做同样的事情,但是您需要调用几个内部的heapify函数,或者更好的是,如larsmans指出的那样,只需复制将_siftup
    / _siftdown从heapq.py转换为您自己的代码:

    h[i] = h[-1]
    h.pop()
    if i < len(h):
        heapq._siftup(h, i)
        heapq._siftdown(h, 0, i)
    

    请注意,在每种情况下您都不能这样做h[i] = h.pop(),因为如果i引用最后一个元素,该操作将失败。如果特殊情况下删除最后一个元素,则可以结合覆盖和弹出。

    请注意,根据堆的典型大小,您可能会发现,仅heapify在理论上效率较低的情况下进行调用可能比重用_siftup/快一些_siftdown:进行一些自省会发现这heapify可能是用C实现的,但是内部函数的C实现没有暴露。如果性能对您很重要,则可以考虑对典型数据进行一些时序测试,以了解哪种方法最好。除非您的堆真的很大,否则大O可能不是最重要的因素。

    编辑: 有人试图编辑此答案,以删除_siftdown带有以下内容的通话:

    不需要_siftdown。保证新h [i]是旧h [i]的最小子项​​,但仍大于旧h [i]的父(新h
    [i]的父)。_siftdown将为空。由于我没有足够的代表来添加评论,因此我必须进行编辑。

    他们在此评论中错过的h[-1]可能根本不是孩子h[i]。插入的新值h[i]可能来自堆的完全不同的分支,因此可能需要沿任一方向进行筛选。

    同样在询问为什么不仅仅用于sort()还原堆的评论中:调用_siftup_siftdown都是O(log
    n)操作,调用heapify就是O(n)。调用sort()是一个O(n log n)操作。调用排序很有可能足够快,但是对于大堆来说,这是不必要的开销。

    编辑 以避免@Seth
    Bruder指出的问题。当i引用end元素时,_siftup()调用将失败,但是在那种情况下,将元素从堆的末端弹出不会破坏堆的不变性。



知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看