eliminación de Java PriorityQueue de elementos arbitrarios de rendimiento

Question

decir que tengo un PriorityQueue java (que Java implementa como un montón) que iterar sobre para eliminar los elementos en base a unos criterios:

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

Cuánto tiempo hace cada remove() toma de operación? No estoy seguro de si es O (log (n)) o O (1).

Answer 1

Si está utilizando la implementación de Sun, es O(log(n)). Desde el Javadocs: nota

Implementación: esta implementación proporciona tiempo O (log (n)) para la enqueing y métodos dequeing (offer, poll, remove() y add); tiempo lineal para los métodos remove(Object) y contains(Object) ; y tiempo constante para los métodos de recuperación (peek, element y size).

Otras implementaciones pueden tener una complejidad diferente.

---

Editar: Los Javadocs no cubren el rendimiento de la eliminación de un elemento con un iterador, así que tuve que buscar el código fuente. Todo esto es relevante para la implementación de Sun, y puede diferir en la versión de Apple, GNU Classpath, etc. La fuente de Sun está disponible here; también está incluido en el JDK, por lo que es posible que ya lo tenga instalado.

En el iterador PriorityQueue 's, el caso predeterminado de remove() es llamar PriorityQueue.removeAt(lastRet), donde lastRet es el índice que fue devuelto por última next(). removeAt() parece ser O(log(n)) peor caso (podría tener que cernir la cola, pero no tiene que iterar).

Sin embargo, a veces suceden cosas malas. A partir de los comentarios de 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. 
*/ 

Cuando un elemento no nulo es devuelto por removeAt(), el iterador añade a una cola especial para su uso posterior: cuando el repetidor se queda sin elementos en la cola, entonces se repite a través de esta cola especial. Cuando se llama a remove() durante esta segunda fase de iteración, el iterador llama a PriorityQueue.removeEq(lastRetElt), donde lastRetElt es el último elemento devuelto de la cola especial. removeEq se ve obligado a utilizar una búsqueda lineal para encontrar el elemento correcto para eliminar, lo que hace que sea O(n). PERO puede verificar elementos usando == en lugar de .equals(), por lo que su factor constante es menor que PriorityQueue.remove(Object).

Por lo tanto, en otras palabras, eliminar con un iterador es técnicamente O(n), pero en la práctica debería ser bastante más rápido que remove(Object).