Java Priorityqueue Entfernung von beliebigen Elementen -leistung

Question

Sagen, ich habe eine Java-Priorityqueue (die Java als Heap implementiert), dass ich iterieren Elemente zu entfernen, auf der Grundlage einiger Kriterien:

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

Wie lange dauert jede remove() Operation nehmen? Ich bin mir nicht sicher, ob es O (log (n)) oder O (1) ist.

Answer 1

Wenn Sie die Sun-Implementierung verwenden, lautet sie O(log(n)). Vom Javadocs:

Implementierung Hinweis: Diese Implementierung stellt O (log (n)) Zeit für die Enqueing und dequeing Methoden (offer, poll, remove() und add); lineare Zeit für die remove(Object) und contains(Object) Methoden; und konstante Zeit für die Abrufmethoden (peek, element und size).

Andere Implementierungen können unterschiedliche Komplexität haben.

---

Edit: Die Javadocs decken nicht die Leistung eines Elements mit einem Iterator zu entfernen, also musste ich den Quellcode schauen. Dies ist alles relevant für die Sun-Implementierung und kann sich in Apples Version, GNU Classpath usw. unterscheiden. Suns Quelle ist verfügbar here; Es ist auch im JDK enthalten, so dass Sie es möglicherweise bereits installiert haben.

In dem PriorityQueue ‚s Iterator, ist der Standardfall für remove()PriorityQueue.removeAt(lastRet) zu nennen, wo lastRet der Index ist, der von next() letzten zurückgekehrt war. removeAt() scheint O(log(n)) worst case (es muss möglicherweise die Warteschlange zu sieben, muss aber nicht iterieren).

Manchmal passieren jedoch schlimme Dinge. Aus den Kommentaren der 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. 
*/ 

Wenn ein Nicht-Null-Element von removeAt() zurückgegeben wird, fügt der Iterator es eine spezielle Warteschlange für eine spätere Verwendung: Wenn der Iterator aus Elementen in der Warteschlange ausgeführt wird, dann iteriert durch diese spezielle Warteschlange. Wenn remove() während dieser zweiten Iterationsphase aufgerufen wird, ruft der Iterator PriorityQueue.removeEq(lastRetElt) auf, wobei lastRetElt das letzte Element ist, das von der speziellen Warteschlange zurückgegeben wird. removeEq ist gezwungen, eine lineare Suche zu verwenden, um das richtige zu entfernende Element zu finden, wodurch es O(n) wird. ABER es kann Elemente mit == anstelle von .equals() überprüfen, so ist sein konstanter Faktor niedriger als PriorityQueue.remove(Object).

Mit anderen Worten, das Entfernen mit einem Iterator ist technisch O(n), aber in der Praxis sollte es ein wenig schneller sein als remove(Object).