¿Cuál es la complejidad (big-oh) para la función remove() en la clase Priority Queue en Java? No puedo encontrar nada documentado en ninguna parte, creo que es O (n), teniendo en cuenta que debes encontrar el elemento antes de eliminarlo y luego reorganizar el árbol. pero he visto a otros que están en desacuerdo y piensan que es O (logn). ¿Algunas ideas?Cola de prioridad eliminar tiempo de complejidad
La complejidad de Remove es O (N) ya que la complejidad para contiene es O (N) (en la clase de cola de prioridad de java)
Una manera en que se pueden hacer O (logN) en su propio Prioridad La implementación de cola es mantener una estructura de datos auxiliares como HashMap que mantiene las asignaciones de un valor en la cola de prioridad a su posición en la cola. Entonces, en cualquier momento dado, sabría la posición del índice de cualquier valor.
Tenga en cuenta que esta modificación no afecta el tiempo de ejecución de ninguna de las operaciones existentes; solo deberá actualizar las asignaciones durante las operaciones de heapify.
Entonces, si conozco la posición del índice de un elemento, ¿cómo lo elimino en la API de Priority Queue basada en el índice? (en el tiempo O (logN)) – novalain
@novalain Desafortunadamente, la API de Java no expone una forma de acceder a los elementos en una cola de prioridad por índice, por lo que deberá usar su propia implementación de cola de prioridad. –
¿Cómo es que O (logN) se elimina de nuestra propia implementación y no O (1)? Estoy seguro de que me faltan algunos detalles, pero una cola de prioridad es solo una estructura de datos clasificada de alta a baja prioridad. Si se implementa utilizando una lista vinculada, y conocemos el índice, ¿no podemos simplemente eliminar ese elemento y conectar el nodo anterior al siguiente nodo? – user3125693
De acuerdo con la documentación de Oracle: "Aplicación nota: esta aplicación proporciona O (log (n)) tiempo para las enqueing y dequeing métodos (oferta, la encuesta, remove() y añadir), el tiempo lineal para los métodos remove (Object) y contains (Object) y el tiempo constante para los métodos de recuperación (peek, element y size). "
Creo que quiso decir eliminar (objeto) no eliminar() el primero es O (n), el último es O (log n) –
'remove()' y 'poll()' son los mismos excepto por la semántica de elemento faltante. La eliminación de un elemento específico ('remove (Object)') es 'O (n)'. Creo que la pregunta no estaba clara y esta es una respuesta válida también ... – TWiStErRob
La confusión es en realidad causada por su función de "eliminar". En Java, hay dos funciones de eliminación.
remove() -> Esto es para eliminar la cabeza/raíz, toma el tiempo O (logN).
remove (Objeto o) -> Esto es para eliminar un objeto arbitrario. Encontrar este objeto toma O (N) tiempo, y eliminarlo toma el tiempo O (logN).
¿Consideró leer el Javadoc? ["esta implementación proporciona el tiempo O (log (n)) para los métodos de enqueing y dequeing (offer, poll, remove() y add)"] (http://docs.oracle.com/javase/6/docs/api) /java/util/PriorityQueue.html). – EJP
Sí, lo hice. En la siguiente línea dice 'tiempo lineal para los métodos remove (Object) y contains (Object); y tiempo constante para los métodos de recuperación (vistazo, elemento y tamaño) ', que era donde me estaba confundiendo. Creo que lo tengo ahora, sin embargo. – samturner