In Java Priority Queue implementation remove at method, why it does a sift up after a sift down?

Question

I have been reading Java collection API, the priority queue part, which is implemented by Josh Bloch and Doug Lea, the two maestros' work.

The Java PriorityQueue is implemented with array heap.

The code snippets are here , from PriorityQueue.java, Line 600：

/**
 * Removes the ith element from queue.
 *
 * Normally this method leaves the elements at up to i-1,
 * inclusive, untouched.  Under these circumstances, it returns
 * null.  Occasionally, in order to maintain the heap invariant,
 * it must swap a later element of the list with one earlier than
 * i.  Under these circumstances, this method returns the element
 * that was previously at the end of the list and is now at some
 * position before i. This fact is used by iterator.remove so as to
 * avoid missing traversing elements.
*/

private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
       if (s == i) // removed last element
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            //the code I am asking is below:
            if (queue[i] == moved) {
               siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

What I am wondered is that, the moved element, which used to be at the bottom of the heap, should be a large one of the sub tree from i. The siftDown method is reasonable, after a siftDown, the smallest of the subtree will be lifted to the position i.

The question is, if the i does not change, i.e. the moved is still there after siftDown, it seems to me that the sub tree has already been heapified, it does not need to be siftUp again.

Why Josh lift them up again to the top?

Hope those who has read the code helps!

Answer 1

The problem is that the moved item (the item at queue[size-1]) might not be in the same subtree as the item that was removed. Consider this heap:

      0
  4       1
5   6   2   3

Now if you remove the node 5 you have:

      0
  4       1
    6   2   3

You take the last node in the heap, 3, and put it in the place where 5 was:

      0
  4       1
3   6   2   

You sift 3 down, but it's already a leaf. It's potentially out of place. You have to sift it up to obtain:

      0
  3       1
4   6   2