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

Question

我一直在阅读Java集合API,这是优先级队列部分,由两位大师的作品Josh Bloch和Doug Lea实现.

Java PriorityQueue是用数组堆实现的.

代码片段来自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方法是合理的,在a之后siftDown,最小的子树将被提升到该位置i.

问题是,如果i没有改变,即移动后仍然存在siftDown,在我看来,子树已经堆积,它不需要siftUp再次.

为什么Josh再次将他们提升到顶峰？

希望那些阅读过代码的人有所帮助!

Answer 1

问题在于，移动的项目（位于的项目queue[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