java - PriorityQueue 的 remove 方法是否重新排列堆？

Question

当在java中remove对一个PriorityQueue对象调用该方法时，堆的头部被移除。要将新的最小元素放在头部，是否对堆的其余部分进行了排序操作？例如，compareTo方法是在什么时候remove被调用的？

抱歉，如果这是在文档中，我在任何地方都找不到。提前致谢。

Answer 1

实现为一个平衡的PriorityQueue二进制堆，实现为一个数组。当一个元素被删除时，堆必须重新排序以保持堆的顺序。

证据在评论里

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
private transient Object[] queue;

同样在类 javadoc

实现说明：此实现为入队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间；remove(Object) 和 contains(Object) 方法的线性时间；检索方法（peek、元素和大小）的恒定时间。

例如remove()，您删除了堆的根。你取最后一个元素，即。二叉树最后一层最右边的叶子，并将其作为根并向下筛选，直到找到它的位置（基于Comparator）。这需要最糟糕的O(log n)时间。

Answer 2

这取决于。如果您正在removeing 数组中支持 的最后一个元素PriorityQueue，则不会进行任何处理。如果您remove有任何其他元素，它将重新排序其元素（siftUp和siftDown）：

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

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);
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}