Java PriorityQueue删除任意元素的性能

Question

假设我有一个java PriorityQueue(java实现为堆),我根据某些条件迭代删除元素:

PriorityQueue q = new PriorityQueue();
...
Iterator it = q.iterator();
while(it.hasNext()){
    if( someCriterion(it.next()) )
        it.remove();
}

每个remove()操作需要多长时间？我不确定它是O(log(n))还是O(1).

Answer 1

如果你正在使用Sun实现,那就是O(log(n)).来自Javadocs:

实现注意事项:此实现提供了O(日志(n))的时间和入队方法dequeing( ,,offer 和); 和 方法的线性时间; 和恒定时间检索方法(,,和).pollremove()addremove(Object)contains(Object)peekelementsize

其他实现可能具有不同的复杂性

编辑: Javadocs没有涵盖使用迭代器删除元素的性能,所以我不得不查找源代码.这一切都与Sun的实现有关,可能在Apple的版本,GNU Classpath等方面有所不同.Sun的源代码可在此处获得 ; 它也包含在JDK中,因此您可能已经安装了它.

在PriorityQueue's迭代器中,默认情况remove()是调用PriorityQueue.removeAt(lastRet),其中lastRet是上次返回的索引next().removeAt()似乎是O(log(n))最糟糕的情况(它可能需要筛选队列,但不必迭代).

但是,有时会发生不好的事情.来自以下评论removeAt():

/**
 * 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.
 */

当返回非null元素时removeAt(),迭代器将其添加到特殊队列以供以后使用:当迭代器耗尽队列中的元素时,它将遍历此特殊队列.在remove()迭代的第二阶段调用时PriorityQueue.removeEq(lastRetElt),迭代器调用,其中lastRetElt是从特殊队列返回的最后一个元素.removeEq被迫使用线性搜索来找到要删除的正确元素,这就是它O(n).但它可以使用==而不是检查元素.equals(),因此它的常数因子低于PriorityQueue.remove(Object).

因此,换句话说,使用迭代器进行删除在技术上是合理的O(n),但实际上它应该比它快得多remove(Object).