Colas de prioridad

Esta técnica también nos permite establecer cotas inferiores al costo de realizar una secuencia de operaciones sobre una estructura de datos.

Por ejemplo, la implementación basada en un heap obtiene tiempos $O(\log n)$ para las operaciones de insertar y extraer el mínimo en una cola de prioridad. Existen implementaciones, como las colas de Fibonacci (que mencionaremos en el capítulo de análisis amortizado) donde la inserción se puede hacer en tiempo $O(1)$, pero la extracción del mínimo aún cuesta $O(\log n)$. Incluso se puede crear un heap de $n$ elementos en tiempo $O(n)$. Nos preguntamos si existirá alguna implementación de colas de prioridad donde se pueda insertar un elemento en tiempo $O(1)$ y extraer el mínimo en tiempo $O(1)$.

No es difícil ver que esto es imposible si se procede por comparaciones. Si lo fuera, podríamos reducir el problema de ordenar $n$ elementos al de insertarlos en una cola de prioridad vacía y extraer el mínimo, luego el mínimo de lo que queda, y así sucesivamente hasta obtener el arreglo ordenado. Si se pudiera extraer el mínimo en tiempo $o(\log n)$, podríamos ordenar en tiempo $o(n\log n)$. Note que esto vale incluso en promedio, si las inserciones agregan los elementos en un orden uniformemente aleatorio.