7

Say I have a java PriorityQueue (which java implements as a heap) that I iterate over to remove elements based on some criteria:

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

How long does each remove() operation take? I'm not sure whether it's O(log(n)) or O(1).

4

1 に答える 1

10

Sun の実装を使用している場合は、O(log(n)). Javadocから:

実装に関する注意: この実装は、エンキューおよびデキュー メソッド ( offer、poll、remove()およびadd) に O(log(n)) 時間を提供します。remove(Object)およびcontains(Object) メソッドの線形時間。検索方法 ( peek、element、およびsize) の定数時間。

他の実装では、複雑さが異なる場合があります。

編集: Javadocs は、イテレータを使用して要素を削除するパフォーマンスをカバーしていないため、ソース コードを調べる必要がありました。これはすべて Sun の実装に関連しており、Apple のバージョン、GNU クラスパスなどによって異なる場合があります。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.
 */

null 以外の要素が によって返されるremoveAt()と、イテレータはそれを後で使用するために特別なキューに追加します。イテレータがキュー内の要素を使い果たすと、この特別なキューを反復処理します。このremove()反復の第 2 段階で が呼び出されると、反復子は を呼び出しますPriorityQueue.removeEq(lastRetElt)。ここlastRetEltで、 は特別なキューから返された最後の要素です。removeEq削除する正しい要素を見つけるために線形検索を使用する必要があるため、O(n). ==しかし、ではなくを使用して要素をチェックできる.equals()ため、その定数係数は よりも低くなりPriorityQueue.remove(Object)ます。

つまり、イテレータによる削除は技術的O(n)には ですが、実際には よりもかなり高速になるはずですremove(Object)。

于 2009-04-16T15:58:53.067 に答える