当在Java中调用PriorityQueue对象的remove方法时,堆的头部将被移除。为了将新的最小元素放在头部,是否对剩余的堆进行任何排序操作?例如,在调用remove时是否调用compareTo方法?
如果这些信息已经在文档中,请见谅,我无法找到它。提前感谢您的帮助。
如果这些信息已经在文档中,请见谅,我无法找到它。提前感谢您的帮助。
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;
remove(Object o)
的源代码,它实际上调用了 indexOf(o)
和 removeAt(i)
,其中前者执行O(n)搜索,后者则进行O(log(n))筛选操作。 - lcnremove
的特定实现并不一定保证所需行为,但感谢提供链接! - templatetypedef这得看情况。如果你 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;
}