Montón mínimo-máximo
En informática , un montón mínimo-máximo es una estructura de datos de árbol binario completa que combina la utilidad de un montón mínimo y un montón máximo , es decir, proporciona recuperación de tiempo constante y eliminación de tiempo logarítmico tanto del mínimo como del máximo. elementos en él. [2] Esto hace que el montón mínimo-máximo sea una estructura de datos muy útil para implementar una cola de prioridad de dos extremos . Al igual que los montones mínimos y máximos binarios, los montones mínimos y máximos admiten la inserción y eliminación logarítmicas y se pueden construir en tiempo lineal. [3] Los montones mínimo-máximo a menudo se representan implícitamente en una matriz ; [4]por lo tanto, se denomina estructura de datos implícita .
La propiedad del montón mínimo-máximo es: cada nodo en un nivel par en el árbol es menor que todos sus descendientes, mientras que cada nodo en un nivel impar en el árbol es mayor que todos sus descendientes . [4]
La estructura también se puede generalizar para soportar otras operaciones de orden de las estadísticas de manera eficiente, tales como find-median, delete-median, [2]find(k) (determinar el k-ésimo valor más pequeño en la estructura) y la operación delete(k)(eliminar el k-ésimo valor más pequeño en la estructura), para cualquier valor fijo (o conjunto de valores) de k . Estas dos últimas operaciones se pueden implementar en tiempo constante y logarítmico, respectivamente. La noción de orden mínimo-máximo puede extenderse a otras estructuras basadas en el orden máximo o mínimo, como los árboles de izquierda , generando una nueva (y más poderosa) clase de estructuras de datos. [4] Un montón mínimo-máximo también puede ser útil al implementar una ordenación rápida externa. [5]
Un montón máximo-mínimo se define de forma análoga; en tal montón, el valor máximo se almacena en la raíz y el valor más pequeño se almacena en uno de los hijos de la raíz. [4]
En las siguientes operaciones asumimos que el montón mínimo-máximo está representado en una matriz A[1..N]; La ubicación en la matriz corresponderá a un nodo ubicado en el nivel del montón.
La creación de un montón mínimo-máximo se logra mediante una adaptación del algoritmo de construcción de montón de tiempo lineal de Floyd, que procede de forma ascendente. [4] Un algoritmo de montón de compilación típico de Floyd [6] es el siguiente:
