Saltar al contenido principal

Colas de Prioridad

En problemas de simulación es común tener que manipular cantidades masivas de eventos que no caben en memoria principal (por ejemplo, colisiones entre partículas, donde cada evento dispara otros eventos que deben simularse más adelante). Si estos eventos se pueden manejar con una cola simple, es muy fácil manejarla en disco a un costo de O(1B)O(\frac{1}{B}) por inserción y borrado. Si, en cambio, deben insertarse para ser procesados en un determinado orden, necesitaremos una cola de prioridad en disco. Un argumento simple de reducción nos muestra que manejar una cola de prioridad en disco requiere Ω(1Blog⁡mn)\Omega(\frac{1}{B}\log_m n) I/Os por operación, pues si no podríamos usarla para ordenar rompiendo la cota inferior que acabamos de demostrar.