Java Priority Queue 实现中的 remove at 方法，为什么它在筛选后进行筛选？

Question

我一直在阅读Java合集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没有变化，即moved在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

Java Priority Queue 实现中的 remove at 方法，为什么它在筛选后进行筛选？

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

java

heap

priority-queue