java - ordenar - elementos de cola de prioridades
Cola de prioridad eliminar tiempo de complejidad (3)
¿Cuál es la complejidad (big-oh) de la función remove() en la clase de cola de prioridad en Java? No puedo encontrar nada documentado en ninguna parte, creo que es O (n), teniendo en cuenta que debe encontrar el elemento antes de eliminarlo y luego reorganizar el árbol. pero he visto a otros que no están de acuerdo y piensan que es O (logn). ¿Algunas ideas?
La complejidad para eliminar es O (N), ya que la complejidad para los contenidos es O (N) (en la clase de cola de prioridad de Java)
Una forma en que esto se puede hacer O (logN) en su propia implementación de la cola de prioridad es mantener una estructura de datos auxiliar como un 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, usted 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 necesitará actualizar las asignaciones durante las operaciones de heapify.
La confusión es en realidad causada por su función "eliminar". En java, hay dos funciones de eliminación.
remove () -> Esto es para eliminar la cabecera / raíz, toma tiempo O (logN).
remove (Object o) -> Esto es para eliminar un objeto arbitrario. Encontrar este objeto lleva tiempo O (N), y eliminarlo requiere tiempo O (logN).
Según la documentación de Oracle: "Nota de implementación: esta implementación proporciona tiempo O (log (n)) para los métodos de encoing y dequeing (ofrecer, sondear, eliminar () y agregar); tiempo lineal para eliminar (Objeto) y contiene (Objeto ) métodos y tiempo constante para los métodos de recuperación (peek, elemento y tamaño) ".