7

假设我有一个 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)。

4

1 回答 1

10

如果您使用的是 Sun 实现，则它是O(log(n)). 从Javadocs：

实现说明：此实现为入队和出队方法（ offer、poll和）提供 O(log(n)) 时间；和 方法的线性时间；检索方法（、和）的固定时间。remove()addremove(Object)contains(Object)peekelementsize

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

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

在PriorityQueue的迭代器中，默认情况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.
 */

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

因此，换句话说，使用迭代器删除在技术上是O(n)，但实际上它应该比remove(Object).

于 2009-04-16T15:58:53.067 回答