Un montón de radix es una estructura de datos para realizar las operaciones de una cola de prioridad monótona . A continuación, se puede gestionar un conjunto de elementos a los que se asigna una clave. El tiempo de ejecución de las operaciones depende de la diferencia entre la clave o constante más grande y más pequeña. La estructura de datos consta principalmente de una serie de depósitos , cuyo tamaño aumenta exponencialmente .
Prerrequisitos
- todas las claves son números naturales ;
- máx. clave - min. clave C para constante C;
- la operación de extracción mínima es monótona; es decir, los valores devueltos por sucesivas llamadas extract-min aumentan monótonamente .
Descripción de la estructura de datos
Los tres campos más importantes son:
- de tamaño , con 0 como índice más bajo, almacena los depósitos;
- de tamaño , con 0 como índice más bajo, almacena los límites (inferiores) de los depósitos;
- , se mantiene para cada elemento en el montón el cubo en el que se almacena.
El diagrama anterior muestra la estructura de datos. Se aplican las siguientes invariantes:
- teclear : las claves en están arriba o abajo a través del valor en o limitado.
- y por : los tamaños de los cubos aumentan exponencialmente.
Es importante tener en cuenta el crecimiento exponencial de los límites (y, por lo tanto, el rango que tiene un cubo). De esta forma, la dependencia logarítmica de las cantidades de campo es de valor C, la diferencia máxima entre dos valores clave.
Operaciones
Durante la inicialización , se generan depósitos vacíos y los límites inferioresse generan (según el invariante 2); tiempo de ejecución.
Durante la inserción , un nuevo elemento se mueve linealmente de derecha a izquierda a través de los cubos y el nuevo elemento con se almacena en el cubo de la izquierda para que ; tiempo de ejecución.
Para la clave de disminución , primero se disminuye el valor de la clave (verificando el cumplimiento de las invariantes). Entonces elEl campo se usa 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).
La operación extract-min elimina un elemento del depósitoy lo devuelve. Si el cuboaún no está vacío, la operación ha finalizado. Sin embargo, si está vacío, se busca el siguiente cubo no vacío más grande, su elemento más pequeño rastreado y se establece en k (se requiere monotonicidad para esto). Luego, de acuerdo con los invariantes, se redefinen los límites del cubo y se eliminan los elementos.a los cubos recién formados; tiempo de ejecución (amortizado).
Si se muestra, el campo se actualiza.
Referencias
- BV Cherkassky, AV Goldberg, C. Silverstein: cubos, montones, listas y colas de prioridad monótona ( resumen ), en: Actas del octavo simposio anual ACM-SIAM sobre algoritmos discretos. Enero de 1997, págs. 83-92.