Clasificación de montón adaptativa

Algoritmo de clasificación basado en comparación

En informática, la clasificación de montón adaptativo es un algoritmo de clasificación basado en comparaciones de la familia de clasificación adaptativa . Es una variante de ordenación en montón que funciona mejor cuando los datos contienen un orden existente. Publicado por Christos Levcopoulos y Ola Petersson en 1992, el algoritmo utiliza una nueva medida de clasificación previa, Osc, como el número de oscilaciones. ^[1] En lugar de colocar todos los datos en el montón como lo hacía la clasificación de montón tradicional, la clasificación de montón adaptativo solo coloca parte de los datos en el montón, de modo que el tiempo de ejecución se reducirá significativamente cuando la clasificación previa de los datos sea alta. ^[1]

clasificación en montón

La clasificación de montón es un algoritmo de clasificación que utiliza una estructura de datos de montón binario . El método trata una matriz como un árbol binario completo y construye un Max-Heap/Min-Heap para lograr la clasificación. ^[2] Por lo general, implica los siguientes cuatro pasos.

1. Cree un Max-Heap (Min-Heap): coloque todos los datos en el montón de modo que todos los nodos sean mayores o iguales (menores o iguales que para Min-Heap ) para cada uno de sus nodos secundarios.
2. Intercambie el primer elemento del montón con el último elemento del montón.
3. Elimina el último elemento del montón y colócalo al final de la lista. Ajuste el montón para que el primer elemento termine en el lugar correcto del montón.
4. Repita los pasos 2 y 3 hasta que el montón tenga un solo elemento. Coloque este último elemento al final de la lista y genere la lista. Los datos de la lista se ordenarán.

A continuación se muestra una implementación de C/C++ que crea un Max-Heap y ordena la matriz una vez creado el montón.

/* Código de clasificación de montón de muestra de AC/C++ que ordena una matriz en orden creciente */// Una función que construye un árbol binario de montón máximo void heapify ( int array [], int start , int end ) { int parent = start ; int hijo = padre * 2 + 1 ; while ( niño <= fin ) { if ( niño + 1 <= fin ) // cuando hay dos nodos secundarios { if ( matriz [ niño + 1 ] > matriz [ niño ]) { niño ++ ; //tomar el nodo hijo más grande } } if ( matriz [ padre ] > matriz [ hijo ]) { return ; //si el nodo padre es mayor, entonces ya está amontonado } if ( matriz [ padre ] < matriz [ hijo ]) // cuando el nodo hijo es mayor que el nodo padre { swap ( matriz [ padre ], matriz [ hijo ]); // cambiar el nodo padre e hijo parent = child ; niño = niño * 2 + 1 ; //continúa el ciclo, compara el nodo hijo y sus nodos hijos } } }                                                    // función heap_sort void heap_sort ( int array [], int len ​​) { for ( int i = len / 2 - 1 ; i >= 0 ; i -- ) //Paso 1: construir el montón máximo { heapify ( matriz , i , len ); } for ( int i = len - 1 ; i >= 0 ; i -- ) //Paso 4: repita los pasos 2 y 3 hasta terminar { swap ( array [ 0 ], array [ i ]); // Paso 2: poner el máximo al final de la matriz heapify ( matriz , 0 , i -1 ); // Paso 3: elimina el máximo del árbol y apila nuevamente } }                                   int principal () { // La matriz que se ordenará int Array [] = { 42 , 1283 , 123 , 654 , 239847 , 45 , 97 , 85 , 763 , 90 , 770 , 616 , 328 , 1444 , 911 , 315 , 38 , 5040 , 1 }; int array_len = tamaño de ( matriz ) / tamaño de ( * matriz ); //longitud de la matriz                         montón_sort ( matriz , matriz_len );  devolver 0 ; } 

Medidas de preclasificación

Las medidas de preclasificación miden el orden existente en una secuencia determinada. ^[3] Estas medidas de clasificación previa deciden la cantidad de datos que se colocarán en el montón durante el proceso de clasificación, así como el límite inferior del tiempo de ejecución. ^[4]

Oscilaciones ( Osc )

Para secuencia , Cruz ( xi ₎ se define como el número de aristas del gráfico lineal de X que son intersecadas por una línea horizontal que pasa por el punto ( i, x _i ). Matemáticamente se define como . La oscilación ( Osc ) de X es solo el número total de intersecciones, definida como . ^[1] ${\displaystyle X=\langle x_{1},x_{2},x_{3},\dots ,x_{n}\rangle }$ ${\displaystyle {\mathit {Cross}}(x_{i})=\{j\mid \min\{x_{j},x_{j+1}\}<x_{i}<\max\{x_{j},x_{j+1}\}{\text{ for }}1\leq j<n\}{\text{, for }}1\leq i\leq n}$ ${\displaystyle {\mathit {Osc}}(x)=\textstyle \sum _{i=1}^{n}\displaystyle \lVert {\mathit {Cross}}(x_{i})\rVert }$

Otras medidas

Además de la medición Osc original, otras medidas conocidas incluyen el número de inversiones Inv , el número de ejecuciones Runs , el número de bloques Block y las medidas Max , Exc y Rem . La mayoría de estas diferentes medidas están relacionadas con la clasificación de montón adaptativo. Algunas medidas dominan a las demás: cada algoritmo Osc-óptimo es Inv óptimo y Runs óptimo; cada algoritmo Inv-óptimo es Max óptimo; y cada algoritmo de bloque óptimo es óptimo Exc y óptimo Rem. ^[4]

Algoritmo

La clasificación de montón adaptativa es una variante de la clasificación de montón que busca la optimización (asintóticamente óptima) con respecto al límite inferior derivado con la medida de preclasificación aprovechando el orden existente en los datos. En la clasificación del montón, para datos , colocamos los n elementos en el montón y luego seguimos extrayendo el máximo (o mínimo) n veces. Dado que el tiempo de cada acción de extracción máxima es logarítmico en el tamaño del montón, el tiempo total de ejecución de la clasificación del montón estándar es . ^[2] Para la clasificación del montón adaptativo, en lugar de colocar todos los elementos en el montón, solo se colocarán en el montón los máximos posibles de datos (candidatos máximos) para que se requieran menos ejecuciones cada vez que intentemos ubicar el montón. máximo (o mínimo). ${\displaystyle X=\langle x_{1},x_{2},x_{3},\dots ,x_{n}\rangle }$ ${\displaystyle \color {Blue}O(n\log n)}$

Primero, se construye un árbol cartesiano a partir de la entrada en el tiempo poniendo los datos en un árbol binario y haciendo que cada nodo del árbol sea mayor (o menor) que todos sus nodos secundarios, y la raíz del árbol cartesiano se inserta en un montón binario vacío. Luego, extraiga repetidamente el máximo del montón binario, recupere el máximo en el árbol cartesiano y agregue sus hijos izquierdo y derecho (si los hay), que son en sí mismos árboles cartesianos, al montón binario. Si la entrada ya está casi ordenada, los árboles cartesianos estarán muy desequilibrados, con pocos nodos que tengan hijos izquierdo y derecho, lo que hará que el montón binario permanezca pequeño y permitirá que el algoritmo ordene más rápidamente que las entradas que ya están casi ordenadas. ^[5] ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$

A continuación se muestra una implementación en pseudocódigo: ^[1]

Entrada: una matriz de n elementos que deben ordenarseConstruir el árbol cartesiano l ( x )Inserte la raíz de l ( x ) en un montónpara i = de 1 a n{ Realizar ExtractMax en el montón si el elemento máximo extraído tiene hijos en l ( x ) { recuperar los niños en l ( x ) inserte el elemento secundario en el montón }}

Desventajas

A pesar de décadas de investigación, todavía existe una brecha entre la teoría de la clasificación adaptativa del montón y su uso práctico. Debido a que el algoritmo utiliza árboles cartesianos y manipulación de punteros, tiene una baja eficiencia de caché y altos requisitos de memoria, los cuales deterioran el rendimiento de las implementaciones. ^[4]

Ver también

• Orden adaptativo
• clasificación en montón
• árbol cartesiano

Referencias

1. Levcopoulos, C.; Petersson, O. (1 de mayo de 1993). "Clasificación de montón adaptativa". Revista de algoritmos . 14 (3): 395–413. doi :10.1006/jagm.1993.1021. ISSN  0196-6774.
2. Schaffer, R.; Sedgewick, R. (1 de julio de 1993). "El análisis de Heapsort". Revista de algoritmos . 15 (1): 76-100. doi :10.1006/jagm.1993.1031. ISSN  0196-6774.
3. Mannila, Heikki (abril de 1985). "Medidas de clasificación previa y algoritmos de clasificación óptimos". Transacciones IEEE en computadoras . C-34 (4): 318–325. doi :10.1109/TC.1985.5009382. ISSN  0018-9340.
4. Edelkamp, ​​Stefan; Elmasry, Amr; Katajainen, Jyrki (2011). "Dos realizaciones óptimas de factor constante de ordenación dinámica adaptativa". En Iliopoulos, Costas S.; Smyth, William F. (eds.). Algoritmos combinatorios . Apuntes de conferencias sobre informática. vol. 7056. Springer Berlín Heidelberg. págs. 195-208. doi :10.1007/978-3-642-25011-8_16. ISBN 9783642250118. S2CID  10325857.
5. "Archivo de códigos interesantes". www.keithschwarz.com . Consultado el 31 de octubre de 2019 .