Cola de prioridad limitada

Consideremos el siguiente esquema. Usaremos la mitad de la memoria, $\frac{M}{2}$, para mantener una cola de prioridad clásica $H$. Todas las inserciones ocurrirán en $H$, gratis. Mientras esta cola no se desborde, no usaremos el disco.

En el momento en que se inserte un nuevo elemento y $H$ esté llena, ésta se ordenará completamente en memoria (gratis) y se almacenará en un archivo en disco, $F_1$, lo que requerirá $\frac{M}{2B}$ escrituras. Inmediatamente crearemos un buffer de tamaño $B$ en memoria para $F_1$, donde leeremos su primer bloque. $H$ quedará vacía de nuevo para aceptar nuevas inserciones.

De ahora en adelante, cada vez que extraigamos el mínimo, tendremos que elegir entre el mínimo de $H$ y el primer elemento del buffer de $F_1$. Una vez que leímos todo el buffer de $F_1$, lo volvemos a llenar leyendo el siguiente bloque de $B$ elementos.

Como $H$ sigue recibiendo inserciones, puede volverse a llenar. En este caso lo ordenamos nuevamente y lo escribimos en un nuevo archivo, $F_2$. En general, tendremos $k$ archivos ordenados $F_1, \ldots, F_k$, y las extracciones de mínimo tendrán que considerar el mínimo entre el mínimo de $H$ y los mínimos de cada $F_i$. Esto se hace fácilmente en tiempo de CPU $O(\log k)$ con una pequeña cola de prioridad que mantiene los primeros elementos de cada $F_i$ y los reemplaza por el siguiente de su buffer cuando éstos son extraídos.

Note que en todo momento los archivos $F_i$ pueden estar a medio leer. Podríamos pensar en un mecanismo más sofisticado que eliminara los archivos leídos, o los uniera cuando se hicieran pequeños, pero aquí mantendremos la simplicidad: los archivos $F_i$ se crean y se van leyendo, y nunca se eliminan o unen.

Considerando que tenemos $\frac{M}{2}$ espacio de memoria para los buffers, tenemos un límite de $k \le \frac{M}{2B}$. Esto significa que tenemos un límite de $N \le k\cdot\frac{M}{2} + \frac{M}{2} \le \frac{M}{2}(\frac{M}{2B}+1) = O(\frac{M^2}{B})$ al total de elementos que pueden ser insertados en esta estructura (en el peor caso; en la práctica muchos podrían eliminarse antes de pasar a un archivo $F_i$). Con una memoria de GBs y un $B$ de KBs, esto equivale a PBs (petabytes).

Para analizar el costo de las operaciones, consideremos lo que nos puede costar un elemento desde que es insertado hasta que es extraído. La inserción es gratis, pero el elemento puede finalmente ser enviado a un archivo $F_i$, donde es escrito junto con otros $B-1$ elementos, por lo que podemos cobrarle $\frac{1}{B}$ escrituras. Luego, puede ser leído de este archivo a su buffer en memoria, junto con otros $B$ elementos, por lo que podemos cobrarle $\frac{1}{B}$ lecturas. En total, cada operación cuesta $O(\frac{1}{B})$ I/Os. Esto, por supuesto, es en un sentido amortizado: muchas operaciones son gratis, y de repente una inserción provoca un costo de $O(\frac{M}{B})$ para escribir un archivo $F_i$ completo. En un esquema más sofisticado, podemos "deamortizar" el costo mediante escribir este archivo poco a poco, dividiendo $H$ en dos colas de tamaño $M/4$, de manera que cuando una se llena empezamos a usar la otra y vamos escribiendo la que se llenó poco a poco a disco, a lo largo de las sucesivas inserciones que siguen. Debemos asegurar que, para cuando la segunda cola se llene, la primera ya se habrá vaciado y puedan intercambiar sus roles.

Aún en sentido amortizado, esta complejidad parece violar la cota inferior: podríamos ordenar en disco en tiempo $O(\frac{N}{B})$ mediante insertar los $N$ elementos y luego extraerlos de esta cola de prioridad. Esto es efectivamente cierto, pero dentro de la limitación de $N = O(\frac{M^2}{B})$. Bajo este supuesto, la complejidad $\Theta(n\log_m \frac{n}{m})$ de ordenar es efectivamente $\Theta(n)$.