Heapsort

En informática, heapsort es un algoritmo de clasificación basado en la comparación. Heapsort se puede considerar como una ordenación por selección mejorada: al igual que la ordenación por selección, heapsort divide su entrada en una región ordenada y otra sin ordenar, y reduce iterativamente la región sin ordenar extrayendo el elemento más grande de ella e insertándolo en la región ordenada. A diferencia de la ordenación por selección, la ordenación heapsort no pierde el tiempo con un escaneo de tiempo lineal de la región no ordenada; más bien, la ordenación en montón mantiene la región no ordenada en una estructura de datos en montón para encontrar más rápidamente el elemento más grande en cada paso.

Aunque en la práctica es un poco más lento en la mayoría de las máquinas que una ordenación rápida bien implementada, tiene la ventaja de un tiempo de ejecución O(n log n) en el peor de los casos más favorable (y como tal, Introsort lo utiliza como respaldo en caso de que detecte que la ordenación rápida se está volviendo degenerada). Heapsort es un algoritmo en el lugar, pero no es una ordenación estable.

Heapsort fue inventado por J. W. J. Williams en 1964. Este fue también el nacimiento del montón, presentado ya por Williams como una estructura de datos útil por derecho propio. En el mismo año, Robert W. Floyd publicó una versión mejorada que podía ordenar una matriz en el lugar, continuando con su investigación anterior sobre el algoritmo de clasificación de árboles.

Resumen

El algoritmo heapsort se puede dividir en dos partes.

En el primer paso, se construye un montón a partir de los datos (ver Montón binario § Construir un montón). El montón a menudo se coloca en una matriz con el diseño de un árbol binario completo. El árbol binario completo mapea la estructura del árbol binario en los índices de matriz; cada índice de matriz representa un nodo; el índice del padre del nodo, la rama secundaria izquierda o la rama secundaria derecha son expresiones simples. Para una matriz de base cero, el nodo raíz se almacena en el índice 0; si i es el índice del nodo actual, entonces

 iParent(i) = piso(i-1) / 2) donde las funciones del suelo mapean un número real al mayor entero líder.
iLeftChild(i) = 2*i + 1
iRightChild(i) = 2*i + 2

En el segundo paso, se crea una matriz ordenada eliminando repetidamente el elemento más grande del montón (la raíz del montón) e insertándolo en la matriz. El montón se actualiza después de cada eliminación para mantener la propiedad del montón. Una vez que se han eliminado todos los objetos del montón, el resultado es una matriz ordenada.

Heapsort se puede realizar en el lugar. La matriz se puede dividir en dos partes, la matriz ordenada y el montón. El almacenamiento de montones como arreglos se representa aquí. El invariante del montón se conserva después de cada extracción, por lo que el único costo es el de la extracción.

Algoritmo

El algoritmo heapsort consiste en preparar la lista convirtiéndola primero en un montón máximo. Luego, el algoritmo intercambia repetidamente el primer valor de la lista con el último valor, disminuyendo el rango de valores considerados en la operación del montón en uno, y tamizando el nuevo primer valor en su posición en el montón. Esto se repite hasta que el rango de valores considerados es de un valor de longitud.

Los pasos son:

1. Llama a la buildMaxHeap() función en la lista. También se menciona como heapify(), esto construye un montón de una lista en ${displaystyle O(n)}$ operaciones.
2. Cambie el primer elemento de la lista con el elemento final. Disminuir el rango considerado de la lista por uno.
3. Llama a la siftDown() función en la lista para sift el nuevo primer elemento a su índice apropiado en el montón.
4. Ir al paso (2) a menos que el rango considerado de la lista sea un elemento.

La operación buildMaxHeap() se ejecuta una vez, y tiene un rendimiento O(n). La función siftDown() es O(log n), y se llama n veces. Por lo tanto, el rendimiento de este algoritmo es O(n + n log n) = O(n registro n).

Pseudocódigo

La siguiente es una forma sencilla de implementar el algoritmo en pseudocódigo. Los arreglos están basados en cero y swap se usa para intercambiar dos elementos del arreglo. Movimiento 'abajo' significa desde la raíz hacia las hojas, o de índices más bajos a más altos. Tenga en cuenta que durante la ordenación, el elemento más grande está en la raíz del montón en a[0], mientras que al final de la ordenación, el elemento más grande está en a[end]< /código>.

procedimiento heapsort(a, count) es entrada: un array sin orden a de longitud Cuenta (Construir el montón en array a para que el valor más grande está en la raíz)heapify(a, count)

 (El siguiente bucle mantiene los invariantes que un[0:end] es un montón y cada elemento más allá del fin es mayor que todo antes (así que un [end:count] está en orden ordenado))final ← contar - 1
 mientras final " 0 do (a[0] es la raíz y el valor más grande. El swap lo mueve delante de los elementos ordenados.)swap(a[end], a[0])
 (el tamaño del montón se reduce por uno)final ← final - 1
 (el swap arruinó la propiedad del montón, así que restaurarlo)siftDown(a, 0, end)

La rutina de clasificación usa dos subrutinas, heapify y siftDown. La primera es la rutina común de construcción de almacenamiento dinámico in situ, mientras que la segunda es una subrutina común para implementar heapify.

(Pon elementos de 'a' en orden de salto, en el lugar)procedimiento heapify(a, count) es (Se asigna el índice en 'a' del último nodo padre) (el último elemento de un array basado en 0 está en el índice conteo-1; encontrar el padre de ese elemento)inicio ← iParent(count-1)

 mientras inicio ≥ 0 do (desciende el nodo en el índice 'comienza' al lugar adecuado tal que todos los nodos abajo  el índice de inicio está en orden de salto)siftDown(a, start, count - 1)
 (ir al siguiente nodo padre)inicio ← inicio - 1
 (después de derribar la raíz todos los nodos/elementos están en orden de salto)(Reparar el montón cuyo elemento raíz está en el índice 'start', asumiendo que los montones arraigados en sus hijos son válidos)procedimiento siftDown(a, start, end) esroot ← start

 mientras iLeftChild(root) ≤ end do (Mientras que la raíz tiene al menos un niño)niño ← iLeftChild(root) (Niño izquierdo de raíz)swap ← root (Keeps Track of child to swap with) si a[swap] entoncesintercambio ← niño
 (Si hay un niño adecuado y ese niño es mayor) si niño+1 ≤ final y a[swap] entoncesintercambio ← niño + 1
 si swap = root entonces (La raíz contiene el elemento más grande. Desde que asumimos los montones arraigados en el  los niños son válidos, esto significa que hemos terminado.) retorno másSwap(a[root], a[swap])
root ← swap (Repeat to continue sifting down the child now)

Se puede pensar en el procedimiento heapify como la construcción de un montón de abajo hacia arriba mediante tamizados sucesivos hacia abajo para establecer la propiedad del montón. Una versión alternativa (que se muestra a continuación) que construye el montón de arriba hacia abajo y tamiza hacia arriba puede ser más fácil de entender. Esta versión de siftUp se puede visualizar comenzando con un montón vacío e insertando elementos sucesivamente, mientras que la versión de siftDown anterior trata la matriz de entrada completa como un archivo completo pero " roto" montón y "reparaciones" comienza desde el último submontón no trivial (es decir, el último nodo principal).

Diferencia en la complejidad del tiempo entre la versión "siftDown" y la versión "siftUp".

Además, la versión siftDown de heapify tiene una complejidad de tiempo O(n), mientras que la versión siftUp que se muestra a continuación tiene O(n log n) complejidad temporal debido a su equivalencia con la inserción de cada elemento, uno a la vez, en un montón vacío. Esto puede parecer contrario a la intuición ya que, de un vistazo, es evidente que el primero solo hace la mitad de llamadas a su función de tamizado de tiempo logarítmico que el segundo; es decir, parecen diferir solo por un factor constante, que nunca afecta el análisis asintótico.

Para comprender la intuición detrás de esta diferencia en complejidad, tenga en cuenta que la cantidad de intercambios que pueden ocurrir durante cualquier siftUp call aumenta con la profundidad del nodo en el que se realiza la llamada. El quid es que hay muchos (exponencialmente muchos) más "profundos" nodos que hay "superficiales" nodos en un montón, de modo que siftUp pueda tener su tiempo de ejecución logarítmico completo en el número aproximadamente lineal de llamadas realizadas en los nodos en o cerca del "inferior" del montón Por otro lado, la cantidad de intercambios que pueden ocurrir durante cualquier llamada siftDown disminuye a medida que aumenta la profundidad del nodo en el que se realiza la llamada. Por lo tanto, cuando siftDown heapify comienza y está llamando a siftDown en la parte inferior y en las capas de nodos más numerosas, cada llamada de tamizado incurrirá, como máximo, un número de intercambios igual a la "altura" (desde la parte inferior del montón) del nodo en el que se realiza la llamada de tamizado. En otras palabras, aproximadamente la mitad de las llamadas a siftDown tienen como máximo un solo intercambio, entonces alrededor de una cuarta parte de las llamadas tendrán como máximo dos intercambios, etc.

El algoritmo heapsort en sí tiene una complejidad de tiempo O(n log n) utilizando cualquier versión de heapify.

 procedimiento heapify(a,count) is
 (El fin se asigna el índice del primer (izquierda) niño de la raíz)final:= 1

 mientras final
 (descargar el nodo en el índice final al lugar apropiado tal que todos los nodos arriba  el índice final está en orden de salto)siftUp(a, 0, end)
final:= final + 1
 (después de subir el último nodo todos los nodos están en orden de salto) procedimiento siftUp(a, start, end) es entrada:  start representa el límite de hasta qué punto el montón de sift. El fin es el nodo para subir.niño:= final
 mientras inicio de niño
parent:= iParent(child)
 si a [parente] entonces (de la orden máxima de salto)swap(a [parente], a[child])
niño:= padre (Repeat to continue sifting up the parent now) más retorno

Tenga en cuenta que, a diferencia del enfoque siftDown en el que, después de cada intercambio, debe llamar solo a la subrutina siftDown para reparar el montón roto; la subrutina siftUp por sí sola no puede arreglar el montón roto. El montón debe construirse cada vez que se realiza un intercambio llamando al procedimiento heapify ya que "siftUp" asume que el elemento que se intercambia termina en su lugar final, a diferencia de "siftDown" permite ajustes continuos de elementos inferiores en el montón hasta que se satisface el invariante. El pseudocódigo ajustado para usar el enfoque siftUp se proporciona a continuación.

 procedimiento heapsort(a, count) es entrada: un array sin orden a de longitud Cuenta (Construir el montón en array a para que el valor más grande está en la raíz)heapify(a, count)

 (El siguiente bucle mantiene los invariantes que un[0:end] es un montón y cada elemento más allá del fin es mayor que todo antes (así que un [end:count] está en orden ordenado))final ← contar - 1
 mientras final " 0 do (a[0] es la raíz y el valor más grande. El swap lo mueve delante de los elementos ordenados.)swap(a[end], a[0])
 (reconstruye el montón usando siftUp después de que el swap arruina la propiedad del montón)heapify(a, end)
 (reducir el tamaño del montón por uno)final ← final - 1

Variaciones

Construcción de montón de Floyd

La variación más importante del algoritmo básico, que se incluye en todas las implementaciones prácticas, es un algoritmo de construcción en montón de Floyd que se ejecuta en O(n) tiempo y usa siftdown en lugar de siftup, evitando la necesidad de implementar siftup en absoluto.

En lugar de comenzar con un montón trivial y agregar hojas repetidamente, el algoritmo de Floyd comienza con las hojas, observa que son montones triviales pero válidos por sí mismos, y luego agrega los padres. Comenzando con el elemento n/2 y trabajando hacia atrás, cada nodo interno se convierte en la raíz de un montón válido al tamizar hacia abajo. El último paso es tamizar el primer elemento, después de lo cual toda la matriz obedece a la propiedad del montón.

Se sabe que el número de comparaciones en el peor de los casos durante la fase de construcción del montón de Floyd es igual a 2n − 2s2(n) − e2(n), donde s2(n) es el número 1 bits en la representación binaria de n y e 2(n) es el número de 0 bits finales.

La implementación estándar del algoritmo de construcción de montones de Floyd provoca una gran cantidad de errores de caché una vez que el tamaño de los datos supera el de la caché de la CPU. Se puede obtener un rendimiento mucho mejor en grandes conjuntos de datos fusionando en primer orden en profundidad, combinando submontones lo antes posible, en lugar de combinar todos los submontones en un nivel antes de continuar con el anterior.

Heapsort de abajo hacia arriba

Heapsort de abajo hacia arriba es una variante que reduce la cantidad de comparaciones requeridas por un factor significativo. Mientras que heapsort ordinario requiere 2n log2 n + O(n) compara el peor de los casos y, en promedio, la variante ascendente requiere n log2 n + O(1) comparaciones en promedio, y 1.5n log 2n + O(n) en el peor de los casos.

Si las comparaciones son baratas (p. ej., claves enteras), la diferencia no es importante, ya que el heapsort de arriba hacia abajo compara valores que ya se han cargado desde la memoria. Sin embargo, si las comparaciones requieren una llamada de función u otra lógica compleja, entonces la clasificación heapsort de abajo hacia arriba es ventajosa.

Esto se logra mejorando el procedimiento siftDown. El cambio mejora un poco la fase de creación de almacenamiento dinámico en tiempo lineal, pero es más significativo en la segunda fase. Como heapsort ordinario, cada iteración de la segunda fase extrae la parte superior del montón, a[0], y llena el espacio que deja con a[end], luego tamiza este último elemento en el montón. Sin embargo, este elemento proviene del nivel más bajo del montón, lo que significa que es uno de los elementos más pequeños del montón, por lo que es probable que el tamizado hacia abajo requiera muchos pasos para volver a bajarlo. En el heapsort ordinario, cada paso del tamizado requiere dos comparaciones, para encontrar el mínimo de tres elementos: el nuevo nodo y sus dos hijos.

Heapsort de abajo hacia arriba encuentra la ruta de los hijos más grandes al nivel de la hoja del árbol (como si estuviera insertando −∞) usando solo una comparación por nivel. Dicho de otro modo, encuentra una hoja que tiene la propiedad de que ella y todos sus ancestros son mayores o iguales a sus hermanos. (En ausencia de claves iguales, esta hoja es única). Luego, desde esta hoja, busca hacia arriba (usando una comparación por nivel) para encontrar la posición correcta en esa ruta para insertar a[fin]. Esta es la misma ubicación que los hallazgos ordinarios de heapsort y requiere la misma cantidad de intercambios para realizar la inserción, pero se requieren menos comparaciones para encontrar esa ubicación.

Debido a que va hasta el fondo y luego vuelve a subir, algunos autores lo llaman heapsort with bounce.

función leafSearch(a, i, end) esj ← i
 mientras iRightChild(j) ≤ end do (Determine cuál de los dos hijos de J es el mayor) si a[iRightChild(j)] ⇩ a[iLeftChild(j)] entoncesj ← iRightChild(j)
 másj ← iLeftChild(j)
 (En el último nivel, sólo puede haber un niño) si iLeftChild(j) ≤ end entoncesj ← iLeftChild(j)
 retorno j

El valor de retorno de leafSearch se usa en la rutina siftDown modificada:

procedimiento siftDown(a, i, end) esj ← leafSearch(a, i, end)
 mientras a[i] doj ← iParent(j)
x ← a[j]
a[j] ← a[i]
 mientras j doswap x, a[iParent(j)]
j ← iParent(j)

Se anunció que la ordenación heap de abajo hacia arriba supera a la ordenación rápida (con una selección de pivote mediana de tres) en arreglos de tamaño ≥16000.

Una reevaluación de este algoritmo en 2008 mostró que no es más rápido que el heapsort ordinario para claves enteras, presumiblemente porque la predicción de bifurcación moderna anula el costo de las comparaciones predecibles que el heapsort de abajo hacia arriba logra evitar.

Un refinamiento adicional realiza una búsqueda binaria en la ruta a la hoja seleccionada y clasifica en el peor de los casos de (n+1)(log 2(n+1) + registro2 registro2(n+1) + 1,82) + comparaciones O(log2n), acercándose al límite inferior teórico de la información de n log2n − 1,4427n comparaciones.

Una variante que utiliza dos bits adicionales por nodo interno (n−1 bits en total para un montón de n elementos) para almacenar en caché información sobre qué hijo es mayor (dos se requieren bits para almacenar tres casos: izquierdo, derecho y desconocido) usa menos de n log2n + 1.1n compara.

Otras variaciones

• Ternary heapsort utiliza un montón ternario en lugar de un montón binario; es decir, cada elemento en el montón tiene tres hijos. Es más complicado programar, pero hace un número constante de veces menos operaciones de intercambio y comparación. Esto se debe a que cada paso hacia abajo en un montón ternario requiere tres comparaciones y un swap, mientras que en un montón binario dos comparaciones y un swap son necesarios. Dos niveles en una cobertura de hebilla ternaria 32 = 9 elementos, haciendo más trabajo con el mismo número de comparaciones que tres niveles en el montón binario, que sólo cubre 23 8. Esto es principalmente de interés académico, o como ejercicio estudiantil, ya que la complejidad adicional no vale la pena de los ahorros menores, y el heapsort de abajo supera ambos.
• Heapsort optimizado para memoria mejora la localidad de referencia de Heapsort aumentando el número de niños aún más. Esto aumenta el número de comparaciones, pero debido a que todos los niños se almacenan consecutivamente en la memoria, reduce el número de líneas de caché accedidas durante el traversal de heap, una mejora neta del rendimiento.
• Out-of-place heapsort mejora en abajo-up heapsort eliminando el peor caso, garantizando n log2n + O()n) comparaciones. Cuando se toma el máximo, en lugar de llenar el espacio vacío con un valor de datos sin surtido, llene con un JUEGO valor centinela, que nunca vuelve a aparecer. Resulta que esto se puede utilizar como un primitivo en un algoritmo "QuickHeapsort" (y no recursivo). En primer lugar, usted realiza un pase de partición de forma rápida, pero reversando el orden de los datos particionados en el array. Suponga (sin pérdida de generalidad) que la partición más pequeña es la más grande que el pivote, que debe ir al final de la matriz, pero nuestro paso de partición inversa lo sitúa al principio. Forma un montón fuera de la partición más pequeña y hacer un surtido fuera de lugar en él, intercambiando la máxima extraída con valores del extremo de la matriz. Estos son menos que el pivote, que significa menos que cualquier valor en el montón, por lo que sirven como JUEGO valores centinela. Una vez que el heapsort está completo (y el pivote se movió a justo antes del extremo ahora surtido de la matriz), el orden de las particiones se ha revertido, y la partición más grande al principio de la matriz se puede ordenar de la misma manera. (Debido a que no hay recidiva de cola, esto también elimina el rápido O(log n) uso de pila.)
• El algoritmo smoothsort es una variación de heapsort desarrollada por Edsger W. Dijkstra en 1981. Como heapsort, liso de banda superior es O()n log n). La ventaja del surtido es que se acerca O()n) tiempo si la entrada ya está clasificada en algún grado, mientras que promedios de heapsort O()n log n) independientemente del estado de orden inicial. Debido a su complejidad, el surtido suave rara vez se utiliza.
• Levcopoulos y Petersson describen una variación de heapsort basada en un montón de árboles cartesianos. Primero, un árbol cartesiano se construye desde la entrada en O()n) tiempo, y su raíz se coloca en un montón binario de 1-element. Luego extraemos repetidamente el mínimo del montón binario, sacamos el elemento raíz del árbol, y agregamos sus hijos izquierdo y derecho (si los hay) que son ellos mismos árboles cartesianos, al montón binario. Como muestran, si la entrada ya está casi ordenada, los árboles cartesianos serán muy desequilibrados, con pocos nodos que tienen niños izquierdos y derecho, resultando en el montón binario restante pequeño, y permitiendo que el algoritmo ordenar más rápido que O()n log n) para los insumos que ya están casi ordenados.
• Varias variantes, como el heapsort débil, requieren n log2 n+O1) comparaciones en el peor de los casos, cerca del mínimo teórico, utilizando un poco extra de estado por nodo. Si bien este bit extra hace que los algoritmos no estén realmente en el lugar, si el espacio para él se puede encontrar dentro del elemento, estos algoritmos son simples y eficientes, pero aún más lento que los montos binarios si las comparaciones clave son lo suficientemente baratas (por ejemplo, claves enteros) que un factor constante no importa.
• Katajainen "ultimo surtido" no requiere almacenamiento extra, realiza n log2 n+O1) comparaciones, y un número similar de movimientos de elementos. Sin embargo, es aún más complejo y no está justificado a menos que las comparaciones sean muy caras.

Comparación con otros tipos

Heapsort compite principalmente con quicksort, otro algoritmo de ordenación basado en comparación in situ y de propósito general muy eficiente.

Las principales ventajas de Heapsort son su código simple, no recursivo, el requisito mínimo de almacenamiento auxiliar y un buen rendimiento confiable: sus mejores y peores casos están dentro de un pequeño factor constante entre sí y del límite inferior teórico en ordenaciones de comparación. Si bien no puede ser mejor que O(n log n) para entradas preordenadas, no sufre de O(n2) de quicksort caso, tampoco. (Esto último se puede evitar con una implementación cuidadosa, pero eso hace que quicksort sea mucho más complejo, y una de las soluciones más populares, introsort, usa heapsort para ese propósito).

Sus principales desventajas son su pobre localidad de referencia y su inherente naturaleza serial; los accesos al árbol implícito están muy dispersos y en su mayoría son aleatorios, y no existe una forma sencilla de convertirlo en un algoritmo paralelo.

Esto lo hace popular en los sistemas integrados, la informática en tiempo real y los sistemas relacionados con entradas seleccionadas de forma malintencionada, como el kernel de Linux. También es una buena opción para cualquier aplicación que no espere cuellos de botella en la clasificación.

Una clasificación rápida bien implementada suele ser de 2 a 3 veces más rápida que una clasificación heap. Aunque quicksort requiere menos comparaciones, este es un factor menor. (Los resultados que reclaman el doble de comparaciones están midiendo la versión de arriba hacia abajo; consulte § Heapsort de abajo hacia arriba). tiene buena localidad temporal. Con un esfuerzo adicional, la ordenación rápida también se puede implementar en la mayoría de los códigos sin bifurcaciones, y se pueden usar varias CPU para ordenar las subparticiones en paralelo. Por lo tanto, se prefiere la ordenación rápida cuando el rendimiento adicional justifica el esfuerzo de implementación.

El otro algoritmo principal de clasificación O(n log n) es la clasificación por combinación, pero que rara vez compite directamente con heapsort porque no está en su lugar. El requisito de clasificación por fusión para Ω(n) espacio adicional (aproximadamente la mitad del tamaño de la entrada) suele ser prohibitivo, excepto en las situaciones en las que merge sort tiene una clara ventaja:

• Cuando se requiere un tipo estable
• Cuando se aprovecha (en parte) de la entrada pre surtido
• Clasificación de listas vinculadas (en qué caso fusionar tipo requiere espacio extra mínimo)
• Ordenación paralela; fusión de tipo paraleliza incluso mejor que rápido y puede lograr fácilmente cerca de la velocidad lineal
• Clasificación externa; fusión tiene excelente localidad de referencia

Ejemplo

Sea { 6, 5, 3, 1, 8, 7, 2, 4 } la lista que queremos ordenar de menor a mayor. (NOTA, para el paso 'Construir el montón': los nodos más grandes no permanecen debajo de los padres de nodo más pequeños. Se intercambian con los padres y luego se verifica recursivamente si se necesita otro intercambio, para mantener los números más grandes arriba números más pequeños en el árbol binario del montón).

Un ejemplo en la variedad de saltos.

Construir el montón

Clasificación