Consultas Teórico/Práctico

Hola Nicolás.

Puede haber muchas implementaciones de cola de prioridad, teniendo compromisos entre distintas operaciones. O sea, en alguna implementación interesa obtener el mínimo en $O(1)$ aún si como consecuencia insertar es $\Theta(n)$. En otra implementación puede ser de interés que insertar sea $O(1)$, y se acepta que eliminar el mínimo sea $\Theta(n)$. Y en otras se puede requerir un equilibrio y que todas las operaciones sean $O(\log n)$.

La implementación estándar para este algoritmo es con un heap que permite remover el mínimo, insertar y actualizar en $O(\log n)$ y obtener el mínimo en $O(1)$.