Clasificación piramidal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de febrero de 2020; las comprobaciones requieren 9 ediciones .

Heap sort ( ing. Heapsort , “Heap sort” [1] ) es un algoritmo de clasificación que funciona en el peor de los casos, en promedio y en el mejor de los casos (es decir, garantizado) para operaciones de clasificación de elementos. [2] La cantidad de memoria back-end utilizada no depende del tamaño de la matriz (es decir, ). $O(n\log n)$ $norte$ $O(1)$

Se puede considerar como una mejora en la clasificación de burbujas , en la que un elemento flota ( min-heap )/se hunde ( max-heap ) en muchas rutas.

Historial de creación

Heapsort fue propuesto por J. Williams en 1964. [una]

Algoritmo

Heapsort utiliza un árbol de clasificación binario . Un árbol de clasificación es un árbol que cumple las siguientes condiciones:

Cada hoja tiene una profundidad de , o , que es la profundidad máxima del árbol. $d$ $d-1$ $d$
El valor en cualquier vértice no es menor (la otra opción no es mayor que) el valor de sus descendientes.

Una estructura de datos conveniente para un árbol de clasificación es una matriz Arraytal que Array[0] es el elemento en la raíz y los hijos del elemento Array[i]son Array[2i+1]y Array[2i+2].

El algoritmo de clasificación constará de dos pasos principales:

1. Construya los elementos de la matriz en forma de árbol de clasificación :

${\text{Matriz}}[i]\geq {\text{Matriz}}[2i+1]$

${\text{Matriz}}[i]\geq {\text{Matriz}}[2i+2]$

en . $0\leq i<n/2$

Este paso requiere cirugía. $En)$

2. Eliminaremos elementos de la raíz uno a la vez y reconstruiremos el árbol. Es decir, en el primer paso, intercambiamos Array[0]y Array[n-1]transformamos Array[0], Array[1], … , Array[n-2]en un árbol de clasificación. Luego reorganizamos Array[0]y Array[n-2]transformamos Array[0], Array[1], … , Array[n-3]en un árbol de clasificación. El proceso continúa hasta que solo queda un elemento en el árbol de clasificación. Entonces Array[0], Array[1], … , Array[n-1] es una sucesión ordenada.

Este paso requiere cirugía. $O(n\log n)$

Ventajas y desventajas

Ventajas

Tiene un límite probado en el peor de los casos . $O(n\cdot\log n)$
Ordena en su lugar, es decir, requiere solo O (1) memoria adicional (si el árbol está organizado como se muestra arriba).

Defectos

Inestable : para garantizar la estabilidad, debe expandir la clave.
En arreglos casi ordenados, toma tanto tiempo como en datos caóticos.
En un paso, la selección debe realizarse aleatoriamente en toda la longitud de la matriz; por lo tanto, el algoritmo no se combina bien con el almacenamiento en caché y el intercambio de memoria .
El método requiere acceso directo "instantáneo"; no funciona en listas enlazadas y otras estructuras de memoria de acceso secuencial.
No paraleliza.

O ( n ) la ordenación por fusión que consume memoria es más rápida ( con una constante más pequeña) y no se degrada con datos incorrectos. $O(n\cdot\log n)$

Debido a la complejidad del algoritmo, la ganancia se obtiene solo para n grande . En n pequeño (hasta varios miles), Shellsort es más rápido .

Aplicación

El algoritmo de "ordenación en montón" se usa activamente en el kernel de Linux .

Notas

↑ 1 2 Curso de conferencias "Tecnologías modernas de programación paralela", Conferencia No. 5: Heap sort (enlace inaccesible) . Consultado el 20 de marzo de 2009. Archivado desde el original el 15 de marzo de 2009. (indefinido)
↑ ScienceDirect - Journal of Algorithms: The Analysis of Heapsort . Consultado el 30 de septiembre de 2017. Archivado desde el original el 4 de junio de 2012. (indefinido)

Literatura

Levitin A.V. Capítulo 6. Método de transformación: Heaps y Heapsort // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 275-284. — 576 pág. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capítulo 6. Heapsort // Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - S. 182-188. — ISBN 5-8459-0857-4 .

Enlaces

Heap sort : una descripción detallada con ilustraciones y una implementación de ejemplo en C ++. Se dan la derivación de estimaciones de la velocidad del algoritmo y la medición del tiempo de ejecución en un sistema informático real.
Clasificación usando un montón (clasificación de montón) : una descripción inteligible con ilustraciones y una implementación de ejemplo en Pascal.
Visualización dinámica 7 Algoritmos de clasificación de código abierto Archivado el 20 de septiembre de 2017 en Wayback Machine .

Algoritmos de clasificación
Teoría	Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio	burbuja Emocionante enanos Rápido Peine Clasificación par-impar bit a bit
Elección	Elección Piramidal Suave
inserciones	inserciones cáscara árbol
fusión	fusión
sin comparaciones	Contando bloquear
híbrido	introsorteo Timsort
Otro	topológico redes bitón
poco práctico	Bogosort Tipo de títere tortita lento