Montículo suave

Para otros usos de este término, véase Montículo (desambiguación).

En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos montículo. Fue concebida por Bernard Chazelle en el año 2000. Al corromper (aumentar) cuidadosamente las claves de a lo sumo un cierto porcentaje fijo de valores en el montículo, logra obtener acceso en tiempo constante amortizado para sus cuatro operaciones:

• create(S): Create un nuevo montículo suave
• insert(S, x): Inserta un elemento en un montículo suave
• meld(S, S' ): Combina el contenido de dos montículo suaves en uno. Ambos parámetros son destruidos en el proceso
• delete(S, x): Borra un elemento de un montículo suave
• findmin(S): Obtiene el elemento de clave mínima en el montículo suave

Otros montículos como el montículo de Fibonacci logran este tipo de cota para algunas operaciones sin necesidad de corromper las claves, sin embargo, no logran acotar de forma constante la crítica operación delete. El porcentaje de valores que son modificados puede ser escogido libremente, pero mientras más bajo sea, más tiempo requieren las inserciones (O(log 1/ε) para una tasa de ε). Las corrupciones bajan efectivamente la entropía de información.

Aplicaciones

Sorprendentemente, los montículos suaves son útiles en el diseño de algoritmos deterministas, a pesar de su naturaleza impredecible. Fueron clave en la creación del mejor algoritmo conocido para calcular el Árbol de expansión mínima. También son utilizados para construir fácilmente un algoritmo de selección óptima, así como algoritmos de casi-ordenamiento que son algoritmos que colocan todo elemento cerca de su posición final, una situación que hace que el algoritmo de ordenamiento por inserción sea muy rápido.

Uno de los ejemplos más sencillo es el algoritmo de selección. Supóngase que se desea encontrar el k-ésimo más grande de un grupo de n números. Primero se escoge una tasa de error de 1/4; es decir, a lo sumo 25% de las claves pueden estar corruptas. Se insertan todos los n elementos en el montículo suave — en este punto, a lo sumo n/4 claves están corruptas. A continuación se borra el elemento mínimo del montículo n/2 veces. Dado que de esta forma se disminuye el tamaño del montículo suave, el total de elementos con clave corrupta sólo puede disminuir. Como resultado se mantiene que a lo sumo n/4 claves están corruptas. Sin embargo, hay también n/4 de las claves que no están corruptas, y deben ser más grandes que todo elemento que de eliminó. Más aún, dado que las claves sólo se aumentan al corromperlas, el último y más grande elemento L que se eliminó debe exceder las claves originales de n/4 de los otros elementos que fueron eliminados. Dicho de otra forma, L divide los elementos en algún lugar entre 25%/75% y 75%/25%. Se particiona el conjunto utilizando L como pivote (paso de partición del algoritmo Quicksort) y se aplica el mismo algoritmo nuevamente a alguno de los dos conjuntos resultantes, cada uno con a lo sumo (3/4)n elementos. Dado que cada inserción y borrado se realiza en tiempo O(1) amortizado, el tiempo total determinista está acotado por un múltiplo de:

T(n) = (5/4)n + (5/4)(3/4)n + (5/4)(3/4)²n + ... = 5n.

El algoritmo final (en wikicode) tiene la siguiente apariencia:

 function softHeapSelect(a[1..n], k)
     if k = 1 then return minimum(a[1..n])
     create(S)
     for i from 1 to n
         insert(S, a[i])
     for i from 1 to n/4
         x := findmin(S)
         delete(S, x)
     xIndex := partition(a, x)
     if k < xIndex
         softHeapSelect(a[1..xIndex-1], k)
     else
         softHeapSelect(a[xIndex..n], k-xIndex+1)

Enlace externo

• Artículo original de Chazelle (pdf) de la página del autor, incluye codificación en lenguaje C.