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) 方法的线性时间；以及检索方法（查看、元素和大小）的恒定时间。

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