Cola de prioridad general

En caso de que debamos manejar más elementos que los permitidos por el esquema anterior (por ejemplo, no siempre la estructura tendrá permitido usar toda la RAM, con lo cual la limitación podría ser más notoria), extenderemos el esquema previo mediante una secuencia creciente de grupos de archivos.

Tendremos un número máximo $k$ de archivos, como antes, pero éstos serán los archivos $F^1_1,\ldots,F^1_k$ del primer grupo. Cuando se intente crear el archivo $F^1_{k+1}$, lo que haremos será unir todos los archivos del grupo actual en uno nuevo, $F^2_1$, de tamaño máximo $k\cdot\frac{M}{2}$. Con ello quedan libres todos los archivos $F^1_i$ y se pueden volver a llenar. Una vez que se creen todos los archivos $F^2_1,\ldots,F^2_k$ y se necesite crear uno nuevo, se unirán todos en un nuevo archivo, $F^3_1$, de tamaño $k^2\cdot\frac{M}{2}$, y se vaciarán todos los $F^2_i$. Y así sucesivamente.

Cada unión de archivos $F^i_1,\ldots,F^i_k$ para construir un $F^{i+1}_j$ cuesta $O(|F^{i+1}_j|/B) = O(k^i m)$, es decir, $O(\frac{1}{B})$ por elemento unido. Si en total construimos $r$ grupos, el costo amortizado de una operación es $O(\frac{r}{B})$, pues a lo largo de su vida en la estructura, un elemento insertado puede ser escrito, luego unido $r-1$ veces, y finalmente leído.

Para poder crear el primer elemento del grupo $r$ debemos haber insertado $N = \sum_{i=0}^{r-1} k^i \cdot \frac{M}{2} = \Theta(k^r M)$ elementos, por lo tanto el número de grupos que podemos llegar a producir es $r = \log_k \frac{N}{M} + O(1)$. Debemos tener $k\cdot r$ buffers en memoria para poder ir extrayendo los mínimos de cada archivo de cada grupo, por lo cual necesitamos que $\frac{M}{2} \ge krB$, es decir, estamos limitados a $2kr \le m$. Para tener tiempo óptimo necesitamos que $r=O(\log_m \frac{n}{m})$, es decir, $\log k = \Theta(\log m)$. Podemos entonces elegir $k=\Theta(m^\alpha)$ para algún $0<\alpha<1$ constante (el costo de las operaciones se multiplicará por $\frac{1}{\alpha}$). Dada la restricción $2kr \le m$, esto significa que debe cumplirse $m^\alpha \log_m n=O(m)$, es decir $\log n = O(m^{1-\alpha}\log m)$.

Esta condición es bastante generosa en la práctica. Por ejemplo, considérese sólo 1 MB de memoria y 1 KB de tamaño de bloque, con lo cual $m = 2^{10}$, y $\alpha=1/2$. Para manejar 1 YBs (un yottabyte, $N=2^{80}$) de datos, usemos $k=m^\alpha=2^5$ y obtenemos $r=\log_k\frac{N}{M} = 12$, con $2kr = 768 < 1024 = m$, y el esquema nos cabe en memoria a sólo el doble del costo óptimo (que sería $\log_m \frac{n}{m} = 6$).