PriorityQueue的remove方法会重新排列堆吗？

Question

当在Java中调用PriorityQueue对象的remove方法时，堆的头部将被移除。为了将新的最小元素放在头部，是否对剩余的堆进行任何排序操作？例如，在调用remove时是否调用compareTo方法？

如果这些信息已经在文档中，请见谅，我无法找到它。提前感谢您的帮助。

- chm

---

我刚刚查阅了文档，没有关于这个问题的具体说明。我很想知道答案！ - templatetypedef

谢谢，很高兴知道我没有错过任何明显的东西！ - chm

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、element和size方法的常数时间。

例如，对于remove()方法，您将删除堆的根。您取最后一个元素，即二叉树最后一层的最右侧叶子，并将其作为根，并进行筛选，直到它找到其位置（基于Comparator）。 这需要最坏的O(log n)时间。

- Sotirios Delimanolis

---

虽然我同意这是需要发生的事情，但文档中是否有任何证明这确实发生了的内容？ - templatetypedef

当它声明自己实现为堆时，必须进行重新排序才能算是堆。否则，它不是堆。您可以查看其余的源代码以了解实现细节。 - Sotirios Delimanolis

@templatetypedef，http://goo.gl/cCKOt3 是 remove(Object o) 的源代码，它实际上调用了 indexOf(o) 和 removeAt(i)，其中前者执行O(n)搜索，后者则进行O(log(n))筛选操作。 - lcn

@lcn- remove 的特定实现并不一定保证所需行为，但感谢提供链接！ - templatetypedef

Answer 2

这得看情况。如果你 remove 的是支持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;
}

- Jeffrey