I recently solved a problem of deleting an element from a middle of a minheap, and a thorough explanation can be found at this StackOverflow article. However it got me wondering, is it possible, instead of swapping the element to be deleted with the rightmost node (or the last element of the underlying array), to instead replace it with the smallest root node (the leftmost element in the underlying array) and instead do a HeapPop, and if so, why is that not done?
Although it could be made to work, it is not a good approach to swap the 𝑖th node with the root node, and then do a HeapPop.
The reason is that:
The HeapPop method actually involves popping the last value from the array and placing it at the root, so that you actually didn't gain anything with respect to the original algorithm. But worse still:
After the root has received its new value, this value needs to sift down to its correct position, but this sift-down path may sometimes traverse to index 𝑖 and swap its value upwards. This means we have to implement extra book-keeping to track the location of where this value ended up being (at 𝑖 or its parent index).
We still need to sift the value that came at index 𝑖 (but possibly moved one level upwards) to its right position -- having saved no work here.
In conclusion: it does not save us from exchanging a value with the last value in the array, involves more sifting work and extra bookkeeping.