python - 从堆 : why siftup and siftdown need to be called? 中移除值

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

不，它实际上复制了索引 ind 处的最后一个元素其中 element被发现，所以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. 我们确定 1 出现在索引 0 ( ind )

2. 值 3 被复制到索引 0，因此堆暂时有一个重复条目:[3, 2, 3]

3. 最后一个条目被删除，所以我们得到 [3, 2]，这是这棵树:

             3
            /
           2
   

4. 由于这棵树违反了堆属性，我们调用heapq._siftdown .该方法会将值 向下 移动 3 直到它位于恢复堆属性的位置。这将导致堆 [2, 3]:

               2
              /
             3
   

示例 2

假设我们有这个(最小)堆:[1, 5, 2, 6, 7, 3] 这是这棵树:

              _1_
            /     \
           5       2
          / \     /
         6   7   3

...我们调用这个函数来删除 6，然后会发生这样的事情:

1. 我们确定 6 出现在索引 3 ( ind )

2. 值 3 被复制到索引 3，所以堆暂时有一个重复的条目:[1, 5, 2, 3, 7, 3]

3. 最后一个条目被删除，所以我们得到 [1, 5, 2, 3, 7]，这是这棵树:

              _1_
            /     \
           5       2
          / \
         3   7   
   

4. 由于这棵树违反了堆属性，我们调用heapq._siftup .该方法会将值 向上 移动 3 直到它位于恢复堆属性的位置。这将导致堆 [1, 3, 2, 5, 7]:

              _1_
            /     \
           3       2
          / \
         5   7   
   

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