Heapsort - Heapsort

Heapsort

Una ejecución de heapsort que ordena una matriz de valores permutados aleatoriamente. En la primera etapa del algoritmo, los elementos de la matriz se reordenan para satisfacer la propiedad del montón . Antes de que tenga lugar la clasificación real, se muestra brevemente la estructura del árbol del montón a modo de ilustración.
Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	${\ Displaystyle O (n \ log n)}$
Rendimiento en el mejor de los casos	${\ Displaystyle O (n \ log n)}$(claves distintas) o (claves iguales)${\ Displaystyle O (n)}$
Rendimiento medio	${\ Displaystyle O (n \ log n)}$
Complejidad espacial en el peor de los casos	${\ Displaystyle O (n)}$auxiliar total${\ Displaystyle O (1)}$

En informática , heapsort es un algoritmo de clasificación basado en comparaciones . Heapsort se puede considerar como un ordenamiento de selección mejorado : como el ordenamiento de selección, heapsort divide su entrada en una región ordenada y una no ordenada, y reduce iterativamente la región no ordenada extrayendo el elemento más grande e insertándolo en la región ordenada. A diferencia del ordenamiento por selección, heapsort no pierde tiempo con un escaneo de tiempo lineal de la región no ordenada; por el contrario, la ordenación del montón mantiene la región sin clasificar en una estructura de datos del montón para encontrar más rápidamente 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 la ventaja de un tiempo de ejecución O ( n log n ) en el peor de los casos más favorable . Heapsort es un algoritmo in situ , pero no es un tipo estable .

Heapsort fue inventado por JWJ 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, RW Floyd publicó una versión mejorada que podría ordenar una matriz en el lugar, continuando su investigación anterior sobre el algoritmo de clasificación de árboles .

Visión general

El algoritmo de clasificación de pilas se puede dividir en dos partes.

En el primer paso, se crea un montón a partir de los datos (consulte Montón binario § Creación de 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 la 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 ies el índice del nodo actual, entonces

  iParent(i)     = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer.
  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.

La clasificación en pila se puede realizar en el lugar. La matriz se puede dividir en dos partes, la matriz ordenada y el montón. Aquí se muestra un diagrama del almacenamiento de montones como matrices . 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 implica 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 en uno el rango de valores considerados en la operación de montón y tamizando el nuevo primer valor en su posición en el montón. Esto se repite hasta que el rango de valores considerados tiene un valor de longitud.

Los pasos son:

1. Llame a la función buildMaxHeap () en la lista. También conocido como heapify (), esto crea un montón a partir de una lista en operaciones O (n).
2. Cambie el primer elemento de la lista con el elemento final. Disminuya el rango considerado de la lista en uno.
3. Llame a la función siftDown () en la lista para tamizar el nuevo primer elemento a su índice apropiado en el montón.
4. Vaya al paso (2) a menos que el rango considerado de la lista sea un elemento.

La operación buildMaxHeap () se ejecuta una vez y su rendimiento es 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 log n ) .

Pseudocódigo

La siguiente es una forma sencilla de implementar el algoritmo en pseudocódigo . Las matrices son de 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 de índices más bajos a 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].

procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (the heap size is reduced by one)
        end ← end - 1
        (the swap ruined the heap property, so restore it)
        siftDown(a, 0, end)

La rutina de clasificación utiliza dos subrutinas heapifyy siftDown. La primera es la rutina común de construcción del montón en el lugar, mientras que la última es una subrutina común para implementar heapify.

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            swap(a[root], a[swap])
            root ← swap            (repeat to continue sifting down the child now)

Se heapifypuede pensar que el procedimiento consiste en construir un montón de abajo hacia arriba mediante el cribado sucesivo 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 simple de entender. Esta siftUpversión se puede visualizar comenzando con un montón vacío e insertando elementos sucesivamente, mientras que la siftDownversión dada arriba trata la matriz de entrada completa como un montón lleno pero "roto" y lo "repara" comenzando desde el último sub-montón no trivial ( es decir, el último nodo padre).

Diferencia de complejidad temporal entre la versión "siftDown" y la versión "siftUp".

Además, la siftDownversión de heapify tiene una complejidad de tiempo O ( n ) , mientras que la siftUpversión dada a continuación tiene una complejidad de tiempo O ( n log n ) 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 sólo hace la mitad de llamadas a su función de cribado de tiempo logarítmico que el segundo; es decir, parecen diferir sólo por un factor constante, que nunca afecta al análisis asintótico.

Para captar la intuición detrás de esta diferencia en complejidad, tenga en cuenta que el número de intercambios que pueden ocurrir durante cualquier llamada siftUp aumenta con la profundidad del nodo en el que se realiza la llamada. El quid es que hay muchos (exponencialmente muchos) nodos más "profundos" que nodos "superficiales" en un montón, por lo que siftUp puede 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 "fondo" del montón. Por otro lado, el número 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 heapifycomienza y está llamando siftDownen la parte inferior y en la mayoría de las capas de nodos, cada llamada de cribado incurrirá, como máximo, en un número de intercambios igual a la "altura" (desde la parte inferior del montón) del nodo en el que se hace la llamada de cribado. En otras palabras, aproximadamente la mitad de las llamadas a siftDown tendrán como máximo un solo intercambio, luego aproximadamente una cuarta parte de las llamadas tendrán como máximo dos intercambios, etc.

El algoritmo de heapsort en sí tiene una complejidad de tiempo O ( n log n ) usando cualquiera de las versiones de heapify.

 procedure heapify(a,count) is
     (end is assigned the index of the first (left) child of the root)
     end := 1
     
     while end < count
         (sift up the node at index end to the proper place such that all nodes above
          the end index are in heap order)
         siftUp(a, 0, end)
         end := end + 1
     (after sifting up the last node all nodes are in heap order)
 
 procedure siftUp(a, start, end) is
     input:  start represents the limit of how far up the heap to sift.
                   end is the node to sift up.
     child := end 
     while child > start
         parent := iParent(child)
         if a[parent] < a[child] then (out of max-heap order)
             swap(a[parent], a[child])
             child := parent (repeat to continue sifting up the parent now)
         else
             return

Tenga en cuenta que, a diferencia del siftDownenfoque, en el que, después de cada intercambio, solo debe llamar a la siftDownsubrutina para reparar el montón roto; la siftUpsubrutina por sí sola no puede arreglar el montón roto. El montón debe construirse cada vez después de un intercambio llamando al heapifyprocedimiento, ya que "siftUp" asume que el elemento que se intercambia termina en su lugar final, a diferencia de "siftDown" permite ajustes continuos de los elementos más bajos en el montón hasta que el invariante se satisface. El pseudocódigo ajustado para usar el siftUpenfoque se muestra a continuación.

 procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (rebuild the heap using siftUp after the swap ruins the heap property)
        heapify(a, end)
        (reduce the heap size by one)
        end ← end - 1

Variaciones

Construcción del 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 de montón de Floyd que se ejecuta en tiempo O ( n ) 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, 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 tamizar 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.

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 de Heapsort es igual a 2 n - 2 s ₂ ( n ) - e ₂ ( n ) , donde s ₂ ( n ) es el número de 1 bits en la representación binaria de n y e ₂ ( n ) es el número de de salida 0 bits.

La implementación estándar del algoritmo de construcción de montón de Floyd provoca una gran cantidad de fallos de caché una vez que el tamaño de los datos excede 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 pasar al anterior.

Heapsort ascendente

La clasificación en pila ascendente es una variante que reduce el número de comparaciones requeridas por un factor significativo. Mientras que el heapsort ordinario requiere 2 n log ₂ n + O ( n ) comparaciones en el peor de los casos y en promedio, la variante ascendente requiere n log ₂ n + O (1) comparaciones en promedio, y 1.5 n log ₂ n + O ( n ) en el peor de los casos.

Si las comparaciones son baratas (por ejemplo, claves de números enteros), entonces la diferencia no es importante, ya que la clasificación de pila 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 en montón ascendente es ventajosa.

Esto se logra mejorando el siftDownprocedimiento. 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. Al igual que el montón ordinario, cada iteración de la segunda fase extrae la parte superior del montón, un [0] , y llena el espacio que deja con un [ final ] , luego tamiza este último elemento en 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 es probable que el tamizado requiera muchos pasos para volver a bajarlo. En la clasificación en pilas ordinaria, cada paso del tamizado requiere dos comparaciones para encontrar el mínimo de tres elementos: el nuevo nodo y sus dos hijos.

En cambio, el heapsort ascendente 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 otra manera, encuentra una hoja que tiene la propiedad de que ella y todos sus antepasados ​​son mayores o iguales que sus hermanos. (En ausencia de claves iguales, esta hoja es única). Luego, desde esta hoja, busca hacia arriba (usando una comparación por nivel) la posición correcta en esa ruta para insertar un [ fin ] . Esta es la misma ubicación que los hallazgos de ordenación en pila ordinarios y requiere el mismo número de intercambios para realizar la inserción, pero se requieren menos comparaciones para encontrar esa ubicación.

Debido a que llega hasta el final y luego vuelve a subir, algunos autores lo llaman heapsort con rebote .

function leafSearch(a, i, end) is
    j ← i
    while iRightChild(j) ≤ end do
        (Determine which of j's two children is the greater)
        if a[iRightChild(j)] > a[iLeftChild(j)] then
            j ← iRightChild(j)
        else
            j ← iLeftChild(j)
    (At the last level, there might be only one child)
    if iLeftChild(j) ≤ end then
        j ← iLeftChild(j)
    return j

El valor de retorno de leafSearchse utiliza en la siftDownrutina modificada :

procedure siftDown(a, i, end) is
    j ← leafSearch(a, i, end)
    while a[i] > a[j] do
        j ← iParent(j)
    x ← a[j]
    a[j] ← a[i]
    while j > i do
        swap x, a[iParent(j)]
        j ← iParent(j)

El heapsort ascendente se anunció como mejor que el quicksort (con una selección de pivote de mediana de tres) en matrices de tamaño ≥16000.

Una reevaluación de este algoritmo en 2008 mostró que no era más rápido que el ordenamiento en memoria dinámico ordinario para claves enteras, presumiblemente porque la predicción de rama moderna anula el costo de las comparaciones predecibles que el ordenamiento en memoria ascendente logra evitar.

Un refinamiento adicional realiza una búsqueda binaria en la ruta a la hoja seleccionada y ordena en el peor de los casos ( n +1) (log ₂ ( n +1) + log ₂ log ₂ ( n +1) + 1.82) + O (log ₂ n ) comparaciones, acercándose al límite inferior de la teoría de la información de n log ₂ n - 1.4427 n comparaciones.

Una variante que usa 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) usa menos que n log ₂ n + 1,1 n se compara.

Otras variaciones

• Heapsort ternario utiliza un montón ternario en lugar de un montón binario; es decir, cada elemento del montón tiene tres hijos. Es más complicado de programar, pero realiza un número constante de veces menos operaciones de intercambio y comparación. Esto se debe a que cada paso de cribado en un montón ternario requiere tres comparaciones y un intercambio, mientras que en un montón binario se requieren dos comparaciones y un intercambio. Dos niveles en un montón ternario cubren 3 ² = 9 elementos, haciendo más trabajo con el mismo número de comparaciones que tres niveles en el montón binario, que solo cubren 2 ³ = 8. Esto es principalmente de interés académico o como un ejercicio para estudiantes , ya que la complejidad adicional no vale la pena los pequeños ahorros, y el ordenamiento en pila de abajo hacia arriba supera a ambos.
• Heapsort optimizado para memoria mejora la localidad de referencia de heapsort aumentando aún más el número de niños. Esto aumenta el número de comparaciones, pero debido a que todos los elementos secundarios se almacenan consecutivamente en la memoria, reduce el número de líneas de caché a las que se accede durante el recorrido del montón, una mejora del rendimiento neto.
• La clasificación de almacenamiento fuera de lugar mejora la clasificación de almacenamiento ascendente eliminando el peor de los casos, lo que garantiza n log ₂ n + O ( n ) comparaciones. Cuando se toma el máximo, en lugar de llenar el espacio vacío con un valor de datos sin clasificar, llénelo con un valor centinela −∞ , que nunca "rebota". Resulta que esto se puede utilizar como una primitiva en un algoritmo "QuickHeapsort" in situ (y no recursivo). Primero, realiza una pasada de partición similar a una clasificación rápida, pero invirtiendo el orden de los datos particionados en la matriz. Supongamos ( sin pérdida de generalidad ) que la partición más pequeña es la mayor que el pivote, que debería ir al final de la matriz, pero nuestro paso de partición inverso la coloca al principio. Forme un montón a partir de la partición más pequeña y haga una clasificación de montón fuera de lugar, intercambiando los máximos extraídos con valores del final de la matriz. Estos son menores que el pivote, lo que significa menos que cualquier valor en el montón, por lo que sirven como valores centinela −∞ . Una vez que se completa el heapsort (y el pivote se mueve justo antes del final ahora ordenado de la matriz), el orden de las particiones se ha invertido y la partición más grande al principio de la matriz se puede ordenar de la misma manera. (Debido a que no hay una recursividad sin cola , esto también elimina el uso de la pila O (log n ) de quicksort ) .
• El algoritmo smoothsort es una variación de heapsort desarrollado por Edsger Dijkstra en 1981. Al igual que heapsort, el límite superior de smoothsort es O ( n log n ) . La ventaja de la ordenación suave es que se acerca más al tiempo O ( n ) si la entrada ya está ordenada en algún grado , mientras que la ordenación en pilas promedia O ( n log n ) independientemente del estado ordenado inicial. Debido a su complejidad, el smoothsort rara vez se usa.
• Levcopoulos y Petersson describen una variación de heapsort basada en un montón de árboles cartesianos . Primero, se construye un árbol cartesiano a partir de la entrada en tiempo O ( n ) y su raíz se coloca en un montón binario de 1 elemento. Luego, extraemos repetidamente el mínimo del montón binario, generamos el elemento raíz del árbol y agregamos sus hijos izquierdo y derecho (si los hay), que son árboles cartesianos, al montón binario. Como muestran, si la entrada ya está casi ordenada, los árboles cartesianos estarán muy desequilibrados, con pocos nodos con hijos izquierdo y derecho, lo que hará que el montón binario permanezca pequeño y permita que el algoritmo ordene más rápidamente que O ( n log n ) para entradas que ya están casi ordenadas.
• Varias variantes, como el ordenamiento dinámico débil, requieren n log ₂ n + O (1) comparaciones en el peor de los casos, cerca del mínimo teórico, utilizando un bit de estado adicional por nodo. Si bien este bit adicional hace que los algoritmos no estén realmente en su lugar, si se puede encontrar espacio para él dentro del elemento, estos algoritmos son simples y eficientes, pero aún más lentos que los montones binarios si las comparaciones de claves son lo suficientemente baratas (por ejemplo, claves enteras) que un el factor constante no importa.
• El "heapsort definitivo" de Katajainen no requiere almacenamiento adicional, realiza n log ₂ n + O (1) 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 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 los tipos de comparación . Si bien no puede hacerlo mejor que O ( n log n ) para entradas preclasificadas, tampoco sufre el peor caso de O ( n ² ) de clasificación rápida . (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 este propósito).

Sus principales desventajas son su escasa localidad de referencia y su naturaleza intrínsecamente 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 .

Esto lo hace popular en sistemas integrados , computación en tiempo real y sistemas relacionados con entradas elegidas maliciosamente, como el kernel de Linux. También es una buena opción para cualquier aplicación que no espere tener un cuello de botella en la clasificación.

Una ordenación rápida bien implementada suele ser de 2 a 3 veces más rápida que la ordenación en pila. Aunque la clasificación rápida requiere menos comparaciones, este es un factor menor. (Los resultados que afirman el doble de comparaciones están midiendo la versión de arriba hacia abajo; consulte § Ordenación de pilas de abajo hacia arriba ). La principal ventaja de la ordenación rápida es su ubicación de referencia mucho mejor: la partición es un escaneo lineal con una buena ubicación espacial y la subdivisión recursiva 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 ramificaciones , y se pueden usar 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 principal de clasificación O ( n log n ) es la clasificación por fusión , pero que rara vez compite directamente con la clasificación de pila porque no está en su lugar. El requisito de la ordenación combinada para Ω ( n ) espacio adicional (aproximadamente la mitad del tamaño de la entrada) suele ser prohibitivo, excepto en las situaciones en las que la ordenación combinada tiene una clara ventaja:

• Cuando se requiere una especie estable
• Al aprovechar la entrada (parcialmente) clasificada previamente
• Ordenar listas enlazadas (en cuyo caso la ordenación por fusión requiere un espacio extra mínimo)
• Clasificación paralela; La ordenación combinada paraleliza incluso mejor que la ordenación rápida y puede alcanzar fácilmente una aceleración cercana a la lineal
• Clasificación externa ; fusionar ordenación tiene una 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 por debajo de los padres de los nodos más pequeños. Se intercambian con los padres y luego se verifican de forma recursiva si se necesita otro intercambio, para mantener números más grandes por encima de los números más pequeños en el árbol binario del montón. .)

Un ejemplo de heapsort.

Notas

Referencias

• Williams, JWJ (1964), "Algorithm 232 - Heapsort", Communications of the ACM , 7 (6): 347–348, doi : 10.1145 / 512274.512284
• Floyd, Robert W. (1964), "Algoritmo 245 - Treesort 3", Comunicaciones del ACM , 7 (12): 701, doi : 10.1145 / 355588.365103 , S2CID  52864987
• Carlsson, Svante (1987), "Average-case results on heapsort", BIT , 27 (1): 2-17, doi : 10.1007 / bf01937350 , S2CID  31450060
• Knuth, Donald (1997), "§5.2.3, Clasificación por selección", Clasificación y búsqueda , El arte de la programación informática , 3 (tercera edición), Addison-Wesley, págs. 144-155, ISBN 978-0-201-89685-5
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN  0-262-03293-7 . Capítulos 6 y 7 respectivamente: Heapsort y colas de prioridad
• Un PDF del artículo original de Dijkstra sobre Smoothsort
• Tutorial de Heaps and Heapsort por David Carlson, St. Vincent College

enlaces externos

• Algoritmos de clasificación animados: clasificación en montón en Wayback Machine (archivado el 6 de marzo de 2015) - demostración gráfica
• Material didáctico sobre Heapsort de Univ. Oldenburg : con texto, animaciones y ejercicios interactivos
• Diccionario de NIST de algoritmos y estructuras de datos: Heapsort
• Heapsort implementado en 12 idiomas
• Clasificación revisada por Paul Hsieh
• Una presentación de PowerPoint que demuestra cómo funciona la ordenación de montón para educadores.
• Estructuras de datos abiertas - Sección 11.1.3 - Clasificación en montón , Pat Morin