从堆中移除值：为什么需要调用 siftup 和 siftdown？

Question

    def remove(self, heap, element):
        ind = heap.index(element)
        heap[ind] = heap[-1]
        del heap[-1]

        if ind < len(heap):
            heapq._siftup(heap, ind)
            heapq._siftdown(heap, 0, ind)

我有一个堆，需要从中删除一个元素。这是我对上面代码的理解：

变量ind获取该元素在堆数组中的索引。
heap[ind] = heap[-1] 将该元素放在顶部
del heap[-1] 删除该元素。

但是其余代码在做什么？

为什么ind会小于堆的长度？我不知道这里发生了什么。

Answer 1

heap[ind] = heap[-1] puts that element at the top

不，它实际上复制了找到 element 的索引 ind 处的最后一个元素，因此 element 实际上被删除了（通过覆盖它）。

Why would ind be less than length of heap?

假设element实际出现在堆中，ind可以是0到len(heap)之间的任何值。因为通过 delete heap[-1] 减少了堆的大小，ind 甚至可以等于 len(heap)，考虑到在删除之后的长度。

所以我们可以有两种可能；或者：

ind == len(heap)：当在堆的最末端发现 element 时会发生这种情况：边界情况。通过 delete heap[-1] 减少了堆的长度，因此我们拥有了这种平等。在这种情况下，没有什么可做的了，因为 delete heap[-1] 删除了必须删除的元素。
ind < len(heap)：这是更通用的情况。在这种情况下，我们 而不是 删除了 element，而是另一个元素。该元素被复制到索引 ind，因此我们实际上通过覆盖它删除了 element...。唯一剩下要做的就是恢复堆属性，这确保一个值不小于其父项且不大于其任何一个子项。

这就是我们需要调用筛选函数的原因。移动到索引 ind 的值可能恰好违反了堆属性.

But what is the code below doing?

一些示例可能会阐明正在发生的事情

示例 1

假设我们有这个（最小）堆：[1, 2, 3] 这是这棵树：

             1
            / \
           2   3

...我们调用这个函数来删除1，那么会发生这样的事情：

我们确定 1 出现在索引 0 (ind)
值3被复制到索引0，所以堆暂时有一个重复项：[3, 2, 3]
去掉最后一个条目，所以我们得到[3, 2]，也就是这棵树：
```
          3
         /
        2
```
由于这棵树违反堆属性，我们调用heapq._siftdown。该方法会将值 3 向下移动，直到它位于堆属性已恢复的位置。这将导致堆 [2, 3]:
```
            2
           /
          3
```

示例 2

假设我们有这个（最小）堆：[1, 5, 2, 6, 7, 3] 这是这棵树：

...我们调用这个函数来删除6，然后是这样：

我们确定 6 出现在索引 3 (ind)
值3被复制到索引3，所以堆中暂时有一个duplicate entry：[1, 5, 2, 3, 7, 3]

去掉最后一个条目，所以我们得到[1, 5, 2, 3, 7]，也就是这棵树：

由于这棵树违反堆属性，我们调用heapq._siftup。该方法会将值 3 up 移动到堆属性已恢复的位置。这将导致堆 [1, 3, 2, 5, 7]:
```
           _1_
         /     \
        3       2
       / \
      5   7   
```

因此，在示例 1 中，我们看到了需要向下筛选的情况，而在示例 2 中，我们看到了需要向上筛选的情况。这就是为什么 both 筛选方法被调用的原因：这样可以确保移动的值将被带到它服从堆属性的位置。请注意，两个方法调用中至多有一个会实际移动元素，而另一个调用是无害的。

从堆中移除值：为什么需要调用 siftup 和 siftdown？

Removing value from heap: why siftup and siftdown need to be called?

python

heap

python-3.x

示例 1

示例 2