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

    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)

I have a heap from which an element needs to be removed. This is my understanding of the above code:

The variable ind gets the index of that element in the heap array.
heap[ind] = heap[-1] puts that element at the top
del heap[-1] deletes that element.

But what is the rest of the code doing?

Why would ind be less than the length of the heap? I have no idea what's going on here.

Solution

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

No, it actually copies the last element at the index ind where element was found, so that element is actually deleted (by overwriting it).

Why would ind be less than length of heap?

Assuming that element actually occurs in the heap, ind can be anything between 0 and len(heap). Because the size of the heap is reduced by doing delete heap[-1], ind could even be equal to len(heap), considering the length after that deletion.

So we can have two possibilities; either:

ind == len(heap): this happens when the element was found at the very end of the heap: a boundary case. By the delete heap[-1] the length of the heap was reduced so that we have this equality. In this case there is nothing more to do, as delete heap[-1] deleted the element that had to be deleted.
ind < len(heap): this is the more generic case. In this case we did not delete the element, but another element. That element was copied to index ind, and so we actually deleted element... by overwriting it. The only thing that remains to do is to restore the heap property, which ensures that a value is not less than its parent and not greater than either of its children.

This is why we need to call a sift function. The value that moved to index ind could happen to be in violation of the heap property.

But what is the code below doing?

Some examples may clarify what is happening

Example 1

Let's say we have this (min) heap: [1, 2, 3] which is this tree:

             1
            / \
           2   3

... and we call this function to delete 1, then this is what happens:

We identify that 1 occurs at index 0 (ind)
The value 3 is copied to index 0, so the heap temporarily has a duplicate entry: [3, 2, 3]
The last entry is removed, so we get [3, 2], which is this tree:
```
          3
         /
        2
```
As this tree violates the heap property, we call heapq._siftdown. That method will move the value 3 down until it is at a place where the heap property is restored. This will result in the heap [2, 3]:
```
            2
           /
          3
```

Example 2

Let's say we have this (min) heap: [1, 5, 2, 6, 7, 3] which is this tree:

... and we call this function to delete 6, then this is what happens:

We identify that 6 occurs at index 3 (ind)
The value 3 is copied to index 3, so the heap temporarily has a duplicate entry: [1, 5, 2, 3, 7, 3]

The last entry is removed, so we get [1, 5, 2, 3, 7], which is this tree:

As this tree violates the heap property, we call heapq._siftup. That method will move the value 3 up until it is at a place where the heap property is restored. This will result in the heap [1, 3, 2, 5, 7]:
```
           _1_
         /     \
        3       2
       / \
      5   7   
```

So in example 1 we see a case where a sift-down was necessary, while in example 2 a sift-up was needed. This is the reason why both sift methods are called: this way it is sure that the moved value will be brought at a position where it obeys the heap property. Note that at most one of the two method calls will actually move the element, while the other call is harmless.