Montón de radix

Un montón de bases es una estructura de datos que permite realizar las operaciones de una cola de prioridad monótona . A continuación, se puede gestionar un conjunto de elementos a los que se les asigna una clave. El tiempo de ejecución de las operaciones depende de la diferencia entre la clave o constante más grande y la más pequeña. La estructura de datos consta principalmente de una serie de contenedores, cuyo tamaño aumenta exponencialmente .

Prerrequisitos

1. todas las claves son números naturales ;
2. tecla máx. - tecla mín. C para C constante; ${\displaystyle \leq }$
3. La operación extract-min es monótona; es decir, los valores devueltos por llamadas extract-min sucesivas aumentan monótonamente .

Descripción de la estructura de datos

Los tres campos más importantes son:

1. ${\displaystyle b}$de tamaño , con 0 como el índice más bajo, almacena los contenedores; ${\displaystyle B:=\lfloor log(C+1)\rfloor +1}$
2. ${\displaystyle u}$de tamaño , con 0 como el índice más bajo, almacena los límites (inferiores) de los depósitos; ${\displaystyle B+1}$
3. ${\displaystyle bNum}$, contiene para cada elemento del montón el depósito en el que está almacenado. ${\displaystyle x}$

El diagrama anterior muestra la estructura de datos. Se aplican las siguientes invariantes:

1. ${\displaystyle u[i]\leq }$tecla en : las teclas en se mueven hacia arriba o hacia abajo a través del valor en o limitado. ${\displaystyle b[i]<u[i+1]}$ ${\displaystyle b[i]}$ ${\displaystyle u[i+1]}$ ${\displaystyle u[i]}$
2. ${\displaystyle u[0]=0,u[1]=u[0]+1,u[B]=\infty }$y para : los tamaños de los cubos aumentan exponencialmente. ${\displaystyle 0\leq u[i+1]-u[i]\leq 2^{i-1}}$ ${\displaystyle i=1,\ldots ,B-1}$

Es importante tener en cuenta el crecimiento exponencial de los límites (y, por lo tanto, del rango que contiene un cubo). De esta manera, la dependencia logarítmica de las magnitudes de campo es de valor C, la diferencia máxima entre dos valores clave.

Operaciones

Durante la inicialización , se generan contenedores vacíos y se generan los límites inferiores (según el invariante 2); tiempo de ejecución . ${\displaystyle u}$ ${\displaystyle O(B)}$

Durante la inserción , un nuevo elemento se mueve linealmente de derecha a izquierda a través de los contenedores y el nuevo elemento se almacena en el contenedor izquierdo en ese momento ; tiempo de ejecución . ${\displaystyle x}$ ${\displaystyle k(x)}$ ${\displaystyle u[i]\geq k(x)}$ ${\displaystyle O(B)}$

Para decrease-key , primero se disminuye el valor de la clave (verificando el cumplimiento de las invariantes). Luego, se utiliza el campo para ubicar el elemento y se itera hacia la izquierda, si es necesario, de manera análoga a la operación de inserción . El tiempo de ejecución es (amortizado). ${\displaystyle bNum}$ ${\displaystyle O(1)}$

La operación extract-min elimina un elemento de un contenedor y lo devuelve. Si el contenedor aún no está vacío, la operación finaliza. Sin embargo, si está vacío, se busca el siguiente contenedor más grande que no esté vacío, se rastrea su elemento más pequeño y se establece en k (para esto se requiere monotonía). Luego, de acuerdo con las invariantes, se redefinen los límites del contenedor y se eliminan los elementos a los contenedores recién formados; tiempo de ejecución (amortizado). ${\displaystyle b[0]}$ ${\displaystyle b[0]}$ ${\displaystyle k}$ ${\displaystyle u[0]}$ ${\displaystyle b[i]}$ ${\displaystyle O(1)}$

Si se muestra, el campo se actualiza. ${\displaystyle bNum}$

Referencias

• BV Cherkassky, AV Goldberg, C. Silverstein: Cubos, montones, listas y colas de prioridad monótonas (resumen), en: Actas del octavo simposio anual ACM-SIAM sobre algoritmos discretos. Enero de 1997, págs. 83-92.