在Java优先级队列实现删除方法中，为什么它在筛选后进行筛选？

Question

我一直在阅读Java collection API，这是优先级队列部分，由两位大师Josh Bloch和Doug Lea实现。

JavaPriorityQueue是用数组堆实现的。

代码片段在这里，来自PriorityQueue.java，第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;
    }

我想知道的是，移动的元素，过去在堆的底部，应该是i子树中的一个大元素。siftDown方法是合理的，在一个siftDown之后，子树中最小的将被提升到位置i。

问题是，如果i没有改变，也就是说，在siftDown之后，被移动的子树仍然存在，在我看来，子树已经被重设了，它不需要再次被重设为siftUp。

为什么乔希又把它们举到了顶端？

希望那些读过代码的人能有所帮助！

Answer 1

问题是移动的项目（队列[size-1]中的项目）可能与被删除的项目不在同一个子树中。考虑这个堆：

      0
  4       1
5   6   2   3

现在，如果移除节点5，您将拥有：

      0
  4       1
    6   2   3

取堆中的最后一个节点，3，并把它放在5的位置：

      0
  4       1
3   6   2   

你筛选了3个，但它已经是一片叶子了。这可能不合适。你必须对其进行筛选，以获得：

      0
  3       1
4   6   2