Permitiendo contracciones

Supongamos ahora una situación más compleja en la que también se pueden eliminar elementos en el arreglo. Un elemento eliminado se reemplaza por el que está en último lugar, de modo que el arreglo se almacene en forma compacta. Queremos evitar el estar almacenando demasiada memoria para un arreglo que alguna vez fue grande pero ahora tiene pocos elementos. Para ello, podemos contraer el arreglo cuando queda muy vacío después de un borrado. Esta es la acción contraria a la expansión que se realiza durante la inserción, y supondremos que también cuesta $n$ escrituras.

El primer impulso puede ser que, una vez que el arreglo tenga tamaño $s > \alpha n$, lo contraigamos a tamaño $\frac{s}{\alpha}$. Sin embargo, si volvemos a insertar inmediatamente, el arreglo se volverá a expandir. Por ello, el costo de esta alternativa puede ser muy alto: cada operación costará $\Theta(n)$ escrituras si se elimina un elemento inmediatamente después de expandir, lo que provoca una contracción, luego se vuelve a insertar, lo que provoca otra expansión, luego se vuelve a eliminar, lo que provoca otra contracción, etc.

Para seguir teniendo costo amortizado constante, establecemos que el arreglo se contraerá solamente cuando $s \ge \beta n$, para cierto $\beta > \alpha$, y entonces se contraerá a tamaño $\gamma n$, para un $1<\gamma<\beta$. Esto garantiza que la memoria máxima a ser usada es $\beta n$. Nos preguntamos ahora cuál es el costo amortizado de una operación.

Esta vez no funciona una función de tipo $\phi = an-bs$. Debemos elegir un esquema algo más complejo: $\phi = |an-bs|$. Tenemos ahora las siguientes operaciones:

• Inserción elemental, a costo $c_i=1$. El valor de $\Delta\phi_i$ es a lo sumo $a$, por lo que una cota superior al costo amortizado es $\hat{c_i} \le 1+a$.
• Borrado elemental (es decir, sin considerar la contracción), a costo $c_i=1$. El valor de $\Delta\phi_i$ es también a lo sumo $a$, por lo que tenemos la misma cota superior $\hat{c_i} \le 1+a$.
• Expansión, a costo $c_i=n$. Esta ocurre cuando $n=s$, y pasaremos de $\phi_{i-1} = |an-bs|=|an-bn|$ a $\phi_i = |an-bs\alpha|=|an-bn\alpha|$. Para que nuestro esquema funcione, la expansión debe darse cuando $an-bn\alpha \ge 0$, es decir, que debe valer $a \ge b\alpha$. En este caso, tenemos $\Delta\phi_i = -b(\alpha-1)n$, y tendremos $\hat{c_i} \le 0$ siempre que $b \ge \frac{1}{\alpha-1}$.
• Contracción, a costo $c_i=n$. Esta ocurre cuando $s \ge \beta n$, y pasaremos de $\phi_{i-1} = |an-bs|$ a $\phi_i = |an-b\gamma n|$. Para que nuestro esquema funcione, la contracción debe darse cuando $an-b\gamma n \le 0$, es decir, que debe valer $a \le b\gamma$. En este caso, tenemos $\phi_{i-1}=bs-an \ge b\beta n-an$ y $\phi_i=b\gamma n-an$, y entonces $\Delta\phi_i \le -b(\beta-\gamma)n$. Por lo tanto, tendremos $\hat{c_i} \le 0$ siempre que $b \ge \frac{1}{\beta-\gamma}$.

Tenemos entonces las condiciones $b\alpha \le a \le b\gamma$, $b \ge \frac{1}{\alpha-1}$ y $b \ge \frac{1}{\beta-\gamma}$. Dado un $\beta$ fijo (relacionado con la memoria máxima que permitimos desperdiciar), queremos minimizar $a$ (pues el costo amortizado es $1+a$). El menor $a$ posible es $a = b \alpha$. Usar el menor $b$ posible implica usar el menor $\gamma$ posible, pues $b \ge \frac{1}{\beta-\gamma}$. Como nuestras desigualdades implican $\gamma \ge \alpha$, elegimos $\gamma = \alpha$. Las nuevas cotas inferiores son $b \ge \frac{1}{\alpha-1}$ y $b \ge \frac{1}{\beta-\alpha}$, que decrecen y crecen, respectivamente, con $\alpha$. Por lo tanto, el óptimo se da cuando $\frac{1}{\alpha-1} = \frac{1}{\beta-\alpha}$, es decir, $\alpha=\frac{\beta+1}{2}$. El costo amortizado es entonces $1+a= 1+b\alpha = 1+\frac{\alpha}{\alpha-1}=\frac{2\alpha-1}{\alpha-1} = \frac{2\beta}{\beta-1}$.

Concluyendo, podemos garantizar un uso máximo de $\beta n$ celdas para almacenar $n$ elementos, permitiendo inserciones y borrados, a un costo amortizado de $\frac{2\beta}{\beta-1}$ por operación. Para lograrlo, cuando insertamos y $s=n$, expandimos el arreglo a $s=\frac{\beta+1}{2} n$, y cuando borramos y $s\ge\beta n$, contraemos el arreglo a $s=\frac{\beta+1}{2} n$. Por ejemplo, podemos elegir $\beta=3$ para obtener un costo amortizado de $\frac{2\cdot 3}{3-1} = 3$. Notar también que el costo amortizado tiende a $2$ para $\beta$ creciente.