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中选择strike>：

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

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

---

Edit:Javadocs没有涵盖使用迭代器删除元素的性能，因此我必须查找源代码。这一切都与Sun的实现有关，可能在苹果的版本、GNU类路径等方面有所不同。Sun的源代码是here；它也包含在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)快很多