En informática , heapsort es un algoritmo de clasificación basado en comparaciones que puede considerarse como "una implementación de clasificación por selección utilizando la estructura de datos correcta ". [3] Al igual que la ordenación por selección, heapsort divide su entrada en una región ordenada y otra sin clasificar, y reduce iterativamente la región sin clasificar 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 en montón no pierde tiempo con un escaneo en tiempo lineal de la región sin clasificar; más bien, la clasificación del montón mantiene la región sin clasificar en una estructura de datos del montón para encontrar de manera eficiente el elemento más grande en cada paso.
Aunque en la práctica es algo más lento en la mayoría de las máquinas que una ordenación rápida bien implementada , tiene las ventajas de una implementación muy simple y un tiempo de ejecución O ( n log n ) más favorable en el peor de los casos . La mayoría de las variantes de clasificación rápida del mundo real incluyen una implementación de heapsort como alternativa en caso de que detecten que la clasificación rápida se está degenerando. Heapsort es un algoritmo local , pero no es una clasificación estable .
Heapsort fue inventado por JWJ Williams en 1964. [4] El artículo también presentó el montón binario como una estructura de datos útil por derecho propio. [5] Ese mismo año, Robert W. Floyd publicó una versión mejorada que podía ordenar una matriz in situ, continuando su investigación anterior sobre el algoritmo de clasificación de árboles . [5]
El algoritmo de clasificación del montón se puede dividir en dos fases: construcción del montón y extracción del montón.
El montón es una estructura de datos implícita que no ocupa espacio más allá del conjunto de objetos a ordenar; la matriz se interpreta como un árbol binario completo donde cada elemento de la matriz es un nodo y los enlaces padre e hijo de cada nodo se definen mediante aritmética simple en los índices de la matriz. Para una matriz de base cero, el nodo raíz se almacena en el índice 0 y los nodos vinculados al nodo ise
iNiñoIzquierdo(i) = 2⋅i + 1 iNiñoDerecho(i) = 2⋅i + 2 iPadre(i) = piso((i−1) / 2)
donde la función suelo redondea hacia abajo al entero anterior. Para obtener una explicación más detallada, consulte Montón binario § Implementación del montón .
Este árbol binario es un montón máximo cuando cada nodo es mayor o igual que sus dos hijos. De manera equivalente, cada nodo es menor o igual que su padre. Esta regla, aplicada en todo el árbol, da como resultado que el nodo máximo se ubique en la raíz del árbol.
En la primera fase, se construye un montón a partir de los datos (consulte Montón binario § Construyendo un montón ).
En la segunda fase, el montón se convierte en una matriz ordenada eliminando repetidamente el elemento más grande del montón (la raíz del montón) y colocándolo al final de 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.
La clasificación en montón normalmente se realiza in situ. Durante la primera fase, la matriz se divide en un prefijo sin clasificar y un sufijo ordenado en montón (inicialmente vacío). Cada paso reduce el prefijo y expande el sufijo. Cuando el prefijo está vacío, esta fase se completa. Durante la segunda fase, la matriz se divide en un prefijo ordenado en montón y un sufijo ordenado (inicialmente vacío). Cada paso reduce el prefijo y expande el sufijo. Cuando el prefijo está vacío, la matriz se ordena.
El algoritmo de clasificación de montón comienza reorganizando la matriz en un montón máximo binario. Luego, el algoritmo intercambia repetidamente la raíz del montón (el elemento más grande que queda en el montón) con su último elemento, que luego se declara como parte del sufijo ordenado. Luego se repara el montón que se dañó al reemplazar la raíz, de modo que el elemento más grande vuelva a estar en la raíz. Esto se repite hasta que solo quede un valor en el montón.
Los pasos son:
heapify()función en la matriz. Esto construye un montón a partir de una matriz en operaciones O ( n ) .siftDown()función en la matriz para mover el nuevo primer elemento a su lugar correcto en el montón.La heapify()operación se ejecuta una vez y su rendimiento es O ( n ) . La siftDown()función se llama n veces y requiere trabajo O (log n ) cada vez. Por lo tanto, el rendimiento de este algoritmo es O ( n + n log n ) = O ( n log n ) .
El corazón del algoritmo es la siftDown()función. Esto construye montones binarios a partir de montones más pequeños y se puede considerar de dos maneras equivalentes:
Para establecer la propiedad max-heap en la raíz, se deben comparar hasta tres nodos (la raíz y sus dos hijos), y el mayor debe convertirse en raíz. Esto se hace más fácilmente encontrando el hijo mayor y luego comparándolo con la raíz. Hay tres casos:
siftDown()operación en el subárbol enraizado en la ex raíz recién degradada.El número de iteraciones en cualquier siftdown()llamada está limitado por la altura del árbol, que es ⌊ log 2 n ⌋ = O (log n ) .
La siguiente es una forma sencilla de implementar el algoritmo en pseudocódigo . Las matrices tienen base cero y swapse utilizan para intercambiar dos elementos de la matriz. El movimiento 'hacia abajo' significa desde la raíz hacia las hojas, o desde índices más bajos hacia más altos. Tenga en cuenta que durante la clasificación, el elemento más grande está en la raíz del montón en a[0], mientras que al final de la clasificación, el elemento más grande está en a[end].
Se ingresa el procedimiento heapsort(a, count) : una matriz desordenada a de longitud count (Construya el montón en la matriz a para que el valor más grande esté en la raíz) amontonar(a, contar) (El siguiente bucle mantiene las invariantes de que a[0:end−1] es un montón, y cada elemento a[end:count−1] más allá de end es mayor que todo lo anterior, es decir, a[end:count−1] es en orden ordenado.) fin ← contar while end > 1 do (el tamaño del montón se reduce en uno) fin ← fin − 1 (a[0] es la raíz y el valor más grande. El intercambio lo mueve delante de los elementos ordenados). intercambiar(a[fin], a[0]) (el intercambio arruinó la propiedad del montón, así que restáurela) tamizar(a, 0, final)
La rutina de clasificación utiliza dos subrutinas heapifyy siftDown. La primera es la rutina común de construcción del montón in situ, mientras que la segunda es una subrutina común para implementar heapify.
(Coloque los elementos de 'a' en orden de montón, en el lugar) el procedimiento heapify(a, count) es (el inicio se inicializa en el primer nodo hoja) (el último elemento en una matriz basada en 0 está en el índice count-1; encontrar el padre de ese elemento) inicio ← iParent(cuenta-1) + 1 while start > 0 do (ir al último nodo que no es del montón) inicio ← inicio − 1 (busque el nodo en el índice 'inicio' hasta el lugar adecuado de modo que todos los nodos debajo del índice inicial estén en orden de montón) tamizar(a, iniciar, contar) (después de examinar la raíz, todos los nodos/elementos están en orden de montón) (Repare el montón cuyo elemento raíz está en el índice 'inicio', asumiendo que los montones enraizados en sus hijos son válidos) El procedimiento siftDown(a, root, end) es while iLeftChild(root) < end do (Mientras la raíz tiene al menos un niño) niño ← iLeftChild(root) (Hijo izquierdo de la raíz) (Si hay un hijo derecho y ese hijo es mayor) si niño+1 < fin y a[niño] < a[niño+1] entonces niño ← niño + 1 si una[raíz] <un[niño] entonces intercambiar(a[raíz], a[niño]) raíz ← hijo (repita para continuar examinando al hijo ahora) else (La raíz contiene el elemento más grande. Dado que podemos asumir que los montones enraizados en los hijos son válidos, esto significa que hemos terminado) .
El heapifyprocedimiento opera construyendo pequeños montones y fusionándolos repetidamente usando siftDown. Comienza con las hojas, observando 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 examinar hacia abajo. El último paso es filtrar el primer elemento, después de lo cual toda la matriz obedece a la propiedad del montón.
Para ver que esto lleva O ( n ) tiempo, cuente el número de siftDowniteraciones en el peor de los casos. La última mitad de la matriz requiere cero iteraciones, el cuarto anterior requiere como máximo una iteración, el octavo anterior requiere como máximo dos iteraciones, el decimosexto anterior requiere como máximo tres, y así sucesivamente.
Visto de otra manera, si asumimos que cada siftDownllamada requiere el número máximo de iteraciones, la primera mitad de la matriz requiere una iteración, el primer cuarto requiere una más (2 en total), el primer octavo requiere otra (3 en total), etcétera.
Esto totaliza n /2 + n /4 + n /8 + ⋯ = n⋅(1/2 + 1/4 + 1/8 + ⋯) , donde la suma infinita es una serie geométrica bien conocida cuya suma es 1 , por tanto el producto es simplemente n .
Lo anterior es una aproximación. Se sabe que el número exacto de comparaciones en el peor de los casos durante la fase de construcción del montón de heapsort es igual a 2 n − 2 s 2 ( n ) − e 2 ( n ) , donde s 2 ( n ) es el número de 1 bits en la representación binaria de n y e 2 ( n ) es el número de bits 0 finales . [6] [7]
Aunque es conveniente pensar en las dos fases por separado, la mayoría de las implementaciones combinan las dos, lo que permite expandir una única instancia siftDownen línea . [8] : Algoritmo H Dos variables (aquí starty end) realizan un seguimiento de los límites del área del montón. La parte de la matriz anterior startno está ordenada, mientras que la parte que comienza en endestá ordenada. La construcción del montón disminuye starthasta que es cero, después de lo cual la extracción del montón disminuye endhasta que es 1 y la matriz está completamente ordenada.
Se ingresa el procedimiento heapsort(a, count) : una matriz desordenada a de longitud count inicio ← piso(cuenta/2) fin ← contar mientras finaliza > 1 hazlo si inicia > 0 entonces (construcción del montón) inicio ← inicio − 1 else (extracción del montón) fin ← fin − 1 intercambiar(a[fin], a[0]) (Lo siguiente es tamizar (a, inicio, fin)) raíz ← inicio mientras iLeftChild(raíz) <fin de hacer niño ← iLeftChild(raíz) (Si hay un hijo correcto y ese hijo es mayor) si niño+1 <fin y a[niño] <a[niño+1] entonces niño ← niño + 1 si una[raíz] <un[niño] entonces intercambiar(a[raíz], a[niño]) raíz ← hijo (repita para continuar examinando al hijo ahora) de lo contrario, romper (volver al bucle exterior)
La descripción anterior utiliza el algoritmo mejorado de construcción de montón de Floyd, que opera en tiempo O ( n ) y utiliza la misma siftDownprimitiva que la fase de extracción de montón. Aunque este algoritmo, al ser más rápido y más sencillo de programar, se utiliza en todas las implementaciones prácticas de clasificación de montón, el algoritmo original de Williams puede ser más fácil de entender y es necesario para implementar una cola de prioridad de montón binario más general .
En lugar de fusionar muchos montones pequeños, el algoritmo de Williams mantiene un único montón al frente de la matriz y agrega repetidamente un elemento adicional mediante una siftUpprimitiva. Al estar al final de la matriz, el nuevo elemento es una hoja y no tiene hijos de los que preocuparse, pero puede violar la propiedad del montón al ser mayor que su padre. En este caso intercambiarlo con su padre y repetir la prueba hasta que el padre sea mayor o no quede ningún padre (hemos llegado a la raíz). En pseudocódigo, esto es:
Se ingresa el procedimiento siftUp(a, end) : a es la matriz, que está ordenada en montón hasta el final-1. El final es el nodo a tamizar. mientras finaliza > 0 padre := iPadre(fin) si a[padre] < a[end] entonces (fuera del orden máximo del montón) intercambiar(a[padre], a[fin]) final: = padre (continuar examinando) de lo contrario regresar El procedimiento heapify(a, count) es (comience con un montón trivial de un solo elemento) final := 1 while end <count (tamizar el nodo al final del índice hasta el lugar adecuado de modo que todos los nodos por encima del índice final estén en orden de montón) tamizar(a, final) fin := fin + 1 (después de examinar el último nodo, todos los nodos están en orden de montón)
Para comprender por qué este algoritmo puede tardar asintóticamente más tiempo en construir un montón ( O ( n log n ) vs. O ( n ) en el peor de los casos), tenga en cuenta que en el algoritmo de Floyd, casi todas las llamadas a siftDownoperaciones se aplican a montones muy pequeños . La mitad de los montones son montones triviales de altura 1 y se pueden omitir por completo, la mitad del resto son montones de altura 2, y así sucesivamente. Solo hay dos llamadas en montones de tamaño n /2 y solo siftDownse realiza una operación en el montón completo de n elementos. La operación promedio general siftDowntoma O (1) tiempo.
Por el contrario, el algoritmo de Williams la mayoría de las llamadas a siftUpse realizan en grandes montones de altura O (log n ) . La mitad de las llamadas se realizan con un tamaño de montón de n /2 o más, las tres cuartas partes se realizan con un tamaño de montón de n /4 o más, y así sucesivamente. Aunque el número promedio de pasos es similar a la técnica de Floyd, [9] : 3 entradas preclasificadas causarán el peor de los casos: cada nodo agregado se filtra hasta la raíz, por lo que la llamada promedio requerirá siftUpaproximadamente (log 2 n − 1)/2 + (log 2 n − 2)/4 + (log 2 n − 3)/8 + ⋯ = log 2 n − (1 + 1/2 + 1/4 + ⋯) = log 2 n − 2 iteraciones.
Debido a que está dominado por la segunda fase de extracción del montón, el algoritmo de clasificación del montón en sí tiene una complejidad temporal O ( n log n ) utilizando cualquiera de las versiones de heapify.
La clasificación de montón ascendente es una variante que reduce el número de comparaciones requeridas en un factor significativo. Mientras que la clasificación de montón "de arriba hacia abajo" ordinaria requiere 2 n log 2 n + O ( n ) comparaciones en el peor de los casos y en promedio, [10] la variante ascendente requiere n log 2 n + O (1) comparaciones en promedio, [ 10] y 1,5 n log 2 n + O ( n ) en el peor de los casos. [11]
Si las comparaciones son baratas (por ejemplo, claves enteras), entonces la diferencia no es importante, [12] ya que la clasificación de montón de arriba hacia abajo compara valores que ya se han cargado desde la memoria. Sin embargo, si las comparaciones requieren una llamada a función u otra lógica compleja, entonces la clasificación de montón ascendente es ventajosa.
Esto se logra mediante el uso de un siftDownprocedimiento más elaborado. El cambio mejora ligeramente la fase de creación de montón en tiempo lineal, [13] pero es más significativo en la segunda fase. Al igual que la clasificación de montón de arriba hacia abajo, cada iteración de la segunda fase extrae la parte superior del montón a[0]y llena el espacio que deja a[end], luego filtra este último elemento por el montón. Pero 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 la criba probablemente requerirá muchos pasos para moverlo hacia abajo. [14] En la clasificación de montón de arriba hacia abajo, cada paso siftDownrequiere dos comparaciones para encontrar el mínimo de tres elementos: el nuevo nodo y sus dos hijos.
La clasificación de montón de abajo hacia arriba reemplaza conceptualmente la raíz con un valor de −∞ y la tamiza usando solo una comparación por nivel (ya que ningún niño puede ser menor que −∞) hasta que se alcanzan las hojas, luego reemplaza el −∞ con el valor correcto. valor y lo examina ( nuevamente, usando una comparación por nivel) hasta encontrar la posición correcta.
Esto coloca la raíz en la misma ubicación que top-down siftDown, pero se requieren menos comparaciones para encontrar esa ubicación. Para cualquier siftDownoperación, la técnica de abajo hacia arriba es ventajosa si el número de movimientos hacia abajo es al menos 2 ⁄ 3 de la altura del árbol (cuando el número de comparaciones es 4 ⁄ 3 veces la altura para ambas técnicas), y Resulta que esto es más que cierto en promedio, incluso para las entradas del peor de los casos. [11]
Una implementación ingenua de este algoritmo conceptual causaría algunas copias de datos redundantes, ya que la poción de filtrado deshace parte del filtrado. Una implementación práctica busca hacia abajo una hoja donde se colocaría −∞ , luego hacia arriba donde debería colocarse la raíz. Finalmente, el recorrido ascendente continúa hasta la posición inicial de la raíz, sin realizar más comparaciones sino intercambiando nodos para completar el reordenamiento necesario. Este formulario optimizado realiza la misma cantidad de intercambios que el formulario de arriba hacia abajo siftDown.
Debido a que llega hasta el final y luego vuelve a subir, algunos autores lo llaman ordenación en montón con rebote . [15]
la función leafSearch(a, i, end) es j ← yo while iRightChild(j) < end do (Determine cuál de los dos hijos de j es mayor) si a[iRightChild(j)] > a[iLeftChild(j)] entonces j ← iNiñoDerecho(j) demás j ← iLeftChild(j) (En el último nivel, puede haber solo un hijo) si iLeftChild(j) <end entonces j ← iLeftChild(j) volver j
El valor de retorno de leafSearchse utiliza en la siftDownrutina modificada: [11]
procedimiento siftDown(a, i, end) es j ← búsquedahoja(a, i, final) mientras que a[i] > a[j] hacer j ← iPadre(j) mientras j > lo hago intercambiar(a[i], a[j]) j ← iPadre(j)
Se anunció que la clasificación en montón ascendente supera a la clasificación rápida (con selección de pivote mediana de tres) en matrices de tamaño ≥16000. [10]
Una reevaluación de este algoritmo en 2008 demostró que no es más rápido que la clasificación de montón de arriba hacia abajo para claves enteras, presumiblemente porque la predicción de rama moderna anula el costo de las comparaciones predecibles que la clasificación de montón de abajo hacia arriba logra evitar. [12]
Un refinamiento adicional realiza una búsqueda binaria en la búsqueda ascendente y ordena en el peor de los casos ( n +1)(log 2 ( n +1) + log 2 log 2 ( n +1) + 1,82) + O (log 2 n ) comparaciones, acercándose al límite inferior de la teoría de la información de n log 2 n − 1,4427 n comparaciones. [dieciséis]
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 (se requieren dos bits para almacenar tres casos: izquierdo, derecho y desconocido) [13 ] usa menos de n log 2 n + 1,1 n en comparación. [17]
Heapsort compite principalmente con Quicksort , otro algoritmo de clasificación inestable basado en comparación in situ de propósito general muy eficiente.
Las principales ventajas de Heapsort son su código simple y no recursivo , su mínimo requisito de almacenamiento auxiliar y su 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 de los tipos de comparación . Si bien no puede funcionar mejor que O ( n log n ) para entradas preclasificadas, tampoco sufre el peor caso de Quicksort O ( n 2 ) .
Las implementaciones de clasificación rápida del mundo real utilizan una variedad de heurísticas para evitar el peor de los casos, pero eso hace que su implementación sea mucho más compleja, y las implementaciones como la introclasificación y la clasificación rápida que anula patrones [29] utilizan la clasificación de heapsort como último recurso si detectan problemas degenerados. comportamiento. Por lo tanto, su rendimiento en el peor de los casos es ligeramente peor que si se hubiera utilizado heapsort desde el principio.
Las principales desventajas de Heapsort son su pobre localidad de referencia y su naturaleza inherentemente serial; los accesos al árbol implícito están muy dispersos y en su mayoría aleatorios, y no existe una forma sencilla de convertirlo en un algoritmo paralelo .
Las garantías de rendimiento en el peor de los casos hacen que el heapsort sea popular en la informática en tiempo real y en sistemas relacionados con entradas elegidas maliciosamente [30] , como el kernel de Linux. [31] La combinación de una implementación pequeña y un rendimiento fiable "suficientemente bueno" lo hacen popular en sistemas integrados y, en general, en cualquier aplicación donde la clasificación no sea un cuello de botella en el rendimiento . Por ejemplo, heapsort es ideal para ordenar una lista de nombres de archivos para su visualización, pero un sistema de gestión de bases de datos probablemente querría un algoritmo de clasificación optimizado más agresivamente.
Una clasificación rápida bien implementada suele ser entre 2 y 3 veces más rápida que una clasificación en montón. [19] [32] Aunque la clasificación rápida requiere menos comparaciones, este es un factor menor. (Los resultados que afirman que hay el doble de comparaciones miden la versión de arriba hacia abajo; consulte § Clasificación en montón de abajo hacia arriba). La principal ventaja de la clasificación rápida es su localidad de referencia mucho mejor: la partición es un escaneo lineal con buena localidad espacial, y la subdivisión recursiva tiene buena localidad temporal. Con un esfuerzo adicional, la clasificación rápida también se puede implementar en código mayoritariamente libre de ramas y se pueden utilizar varias CPU para ordenar subparticiones en paralelo. Por lo tanto, se prefiere la clasificación rápida cuando el rendimiento adicional justifica el esfuerzo de implementación.
El otro algoritmo de ordenación O ( n log n ) importante es el ordenamiento por fusión , pero rara vez compite directamente con el ordenamiento en montón porque no está implementado. El requisito de ordenación por combinación de Ω( n ) espacio adicional (aproximadamente la mitad del tamaño de la entrada) suele ser prohibitivo, excepto en situaciones en las que la ordenación por combinación tiene una clara ventaja:
Los ejemplos ordenan los valores {6, 5, 3, 1, 8, 7, 2, 4} en orden creciente utilizando ambos algoritmos de construcción de montón. Los elementos que se comparan se muestran en negrita . Por lo general, hay dos cuando se tamiza hacia arriba y tres cuando se tamiza hacia abajo, aunque puede haber menos cuando se llega a la parte superior o inferior del árbol.
El nombre que normalmente se le da a este algoritmo, heapsort , oscurece el hecho de que el algoritmo no es más que una implementación de clasificación por selección utilizando la estructura de datos correcta.
A falta de un nombre mejor, llamamos a este programa mejorado 'ordenación en montón con rebote'. '
Escriba una rutina de clasificación similar a heapsort excepto que utiliza un montón ternario.
