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. [1]
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos | (claves distintas) o (claves iguales) |
Rendimiento medio | |
Complejidad espacial en el peor de los casos | total auxiliar |
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. [2] Este fue también el nacimiento del montón, presentado ya por Williams como una estructura de datos útil por derecho propio. [3] 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 . [3]
Descripció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 i
es el índice del nodo actual, entonces
iParent (i) = piso ((i-1) / 2) donde las funciones de piso mapean un número real al entero inicial más pequeño. 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:
- 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).
- Cambie el primer elemento de la lista con el elemento final. Disminuya el rango considerado de la lista en uno.
- Llame a la función siftDown () en la lista para tamizar el nuevo primer elemento a su índice apropiado en el montón.
- 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 swap
se 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]
.
El procedimiento heapsort (a, count) es de entrada: 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) acumular (a, contar) (El siguiente ciclo mantiene los invariantes de que un [0: end] es un montón y cada elemento más allá del final es mayor que todo lo anterior (por lo que un [end: count] está en orden ordenado)) fin ← cuenta - 1 while end> 0 do (a [0] es la raíz y el valor más grande. El intercambio lo mueve delante de los elementos ordenados). intercambio (a [final], a [0]) (el tamaño del montón se reduce en uno) fin ← fin - 1 (el intercambio arruinó la propiedad del montón, así que restáuralo) siftDown (a, 0, end)
La rutina de clasificación utiliza dos subrutinas heapify
y 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
.
(Ponga los elementos de 'a' en orden de pila, en el lugar) procedimiento heapify (a, count) es (al inicio se le asigna el índice en 'a' del último nodo principal) (el último elemento en una matriz basada en 0 es en el índice count-1; encuentra el padre de ese elemento) inicio ← iParent (cuenta-1) while start ≥ 0 do (tamice el nodo en el índice 'start' hasta el lugar correcto de modo que todos los nodos por debajo del índice de inicio estén en orden de pila) siftDown (a, inicio, cuenta - 1) (ir al siguiente nodo padre) inicio ← inicio - 1 (después de tamizar la raíz, todos los nodos / elementos están en orden de pila)(Reparar 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, start, end) es root ← iniciar while iLeftChild (root) ≤ end do (mientras que la raíz tiene al menos un hijo) child ← iLeftChild (root) (hijo izquierdo de root) swap ← root (realiza un seguimiento del hijo con el que intercambiar) si un [intercambio]entonces intercambiar ← niño (Si hay un niño correcto y ese niño es mayor) si niño + 1 ≤ fin y un [intercambio] entonces intercambiar ← niño + 1 if swap = root then (La raíz contiene el elemento más grande. Dado que asumimos que los montones enraizados en los hijos son válidos, esto significa que hemos terminado.) return else swap (un [root], un [swap]) root ← swap (repita para continuar tamizando al niño ahora)
Se heapify
puede 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 siftUp
versión se puede visualizar comenzando con un montón vacío e insertando elementos sucesivamente, mientras que la siftDown
versió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).
Además, la siftDown
versión de heapify tiene una complejidad de tiempo O ( n ) , mientras que la siftUp
versió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. [4] 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
heapify
comienza y está llamando siftDown
en 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 ) utilizando cualquiera de las versiones de heapify.
procedimiento heapify (a, count) es (al final se le asigna el índice del primer hijo (izquierdo) de la raíz) final: = 1 while end(tamice el nodo en el extremo del índice hasta el lugar adecuado de modo que todos los nodos por encima del índice final estén en orden de pila) tamizar (a, 0, fin) fin: = fin + 1 (después de tamizar el último nodo, todos los nodos están en orden de pila) procedimiento siftUp (un extremo, comienzo,) es de entrada: inicio representa el límite de lo lejos hasta el montón para tamizar. El final es el nodo a tamizar. niño: = fin mientras niño> empezar padre: = iParent (hijo) if a [parent] then (out of max-heap order) intercambio (un [padre], un [hijo]) hijo: = padre (repita para continuar examinando al padre ahora) de lo contrario, regrese
Tenga en cuenta que, a diferencia del siftDown
enfoque, en el que, después de cada intercambio, solo debe llamar a la siftDown
subrutina para reparar el montón roto; la siftUp
subrutina por sí sola no puede arreglar el montón roto. El montón debe construirse cada vez después de un intercambio llamando al heapify
procedimiento, 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 siftUp
enfoque se da a continuación.
El procedimiento heapsort (a, count) es de entrada: 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) acumular (a, contar) (El siguiente ciclo mantiene los invariantes de que un [0: end] es un montón y cada elemento más allá del final es mayor que todo lo anterior (por lo que un [end: count] está en orden ordenado)) fin ← cuenta - 1 while end> 0 do (a [0] es la raíz y el valor más grande. El intercambio lo mueve delante de los elementos ordenados). intercambio (a [final], a [0]) (reconstruya el montón usando siftUp después de que el intercambio arruine la propiedad del montón) amontonar (reduce el tamaño del montón en uno) fin ← fin - 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 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 de salida 0 bits. [5]
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 . [6] : 87 Se puede obtener un rendimiento mucho mejor en grandes conjuntos de datos fusionando en primer orden en profundidad , combinando submontones tan pronto como sea posible, en lugar de combinar todos los submontones en un nivel antes de pasar al anterior. [7] [8]
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 ordenamiento en pila ordinario requiere 2 n log 2 n + O ( n ) comparaciones en el peor de los casos y en promedio, [9] la variante ascendente requiere n log 2 n + O (1) comparaciones en promedio, [9] y 1,5 n log 2 n + O ( n ) en el peor de los casos. [10]
Si las comparaciones son baratas (por ejemplo, claves de números enteros) entonces la diferencia no es importante, [11] ya que el heapsort de arriba hacia abajo compara valores que ya han sido cargados desde la memoria. Sin embargo, si las comparaciones requieren una llamada a función u otra lógica compleja, entonces la clasificación en montón ascendente es ventajosa.
Esto se logra mejorando el siftDown
procedimiento. El cambio mejora un poco la fase de creación de montones de tiempo lineal, [12] pero es más significativo en la segunda fase. Como en 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. [13] En la clasificación en pilas ordinaria, cada paso del cribado 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. [10]
Debido a que llega hasta el final y luego vuelve a subir, algunos autores lo llaman heapsort con rebote . [14]
la función leafSearch (a, i, end) es j ← i 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 ← iRightChild (j) demás j ← iLeftChild (j) (En el último nivel, podría haber solo un niño) si iLeftChild (j) ≤ end then j ← iLeftChild (j) volver j
El valor de retorno de leafSearch
se utiliza en la siftDown
rutina modificada : [10]
procedimiento siftDown (a, i, end) es j ← leafSearch (a, i, end) mientras que a [i]> a [j] lo hacen j ← iParent (j) x ← a [j] a [j] ← a [i] mientras j> lo hago intercambiar 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. [9]
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. [11]
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 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. [15]
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) [12 ] utiliza menos de n log 2 n + 1,1 n comparaciones. [dieciséis]
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 2 = 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 3 = 8. [ cita requerida ] Esto es principalmente de interés académico, o como un ejercicio para estudiantes, [17] ya que la complejidad adicional no vale los ahorros menores, y la clasificación de pilas de abajo hacia arriba supera a ambos.
- Heapsort optimizado para memoria [6] : 87 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.
- Heapsort fuera de lugar [18] [19] [13] mejora el heapsort ascendente eliminando el peor de los casos, garantizando n log 2 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). [20] Primero, realiza una pasada de partición similar a una ordenació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 recursividad sin cola , esto también elimina el uso de la pila O (log n ) de quicksort ) .
- El algoritmo smoothsort [21] 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. [ cita requerida ]
- Levcopoulos y Petersson [22] 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. [23] 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 2 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 ello dentro del elemento, estos algoritmos son simples y eficientes, [7] : 40 pero aún más lentos que los montones binarios si las comparaciones de claves son lo suficientemente baratas (p. Ej. claves enteras) que un factor constante no importa. [24]
- El "heapsort definitivo" de Katajainen no requiere almacenamiento adicional, realiza n log 2 n + O (1) comparaciones y un número similar de movimientos de elementos. [25] 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 2 ) 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 embebidos , computación en tiempo real y sistemas relacionados con entradas elegidas maliciosamente, [26] como el kernel de Linux. [27] También es una buena opción para cualquier aplicación que no espere sufrir 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. [6] [28] 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 .)
Montón | elemento recién agregado | intercambiar elementos |
---|---|---|
nulo | 6 | |
6 | 5 | |
sesenta y cinco | 3 | |
6, 5, 3 | 1 | |
6, 5, 3, 1 | 8 | |
6, 5 , 3, 1, 8 | 5, 8 | |
6 , 8 , 3, 1, 5 | 6, 8 | |
8, 6, 3, 1, 5 | 7 | |
8, 6, 3 , 1, 5, 7 | 3, 7 | |
8, 6, 7, 1, 5, 3 | 2 | |
8, 6, 7, 1, 5, 3, 2 | 4 | |
8, 6, 7, 1 , 5, 3, 2, 4 | 1, 4 | |
8, 6, 7, 4, 5, 3, 2, 1 |
Montón | intercambiar elementos | eliminar elemento | matriz ordenada | detalles |
---|---|---|---|---|
8 , 6, 7, 4, 5, 3, 2, 1 | 8, 1 | intercambiar 8 y 1 para eliminar 8 del montón | ||
1, 6, 7, 4, 5, 3, 2, 8 | 8 | eliminar 8 del montón y agregar a la matriz ordenada | ||
1 , 6, 7 , 4, 5, 3, 2 | 1, 7 | 8 | intercambia 1 y 7 ya que no están en orden en el montón | |
7, 6, 1 , 4, 5, 3 , 2 | 1, 3 | 8 | intercambie 1 y 3 ya que no están en orden en el montón | |
7 , 6, 3, 4, 5, 1, 2 | 7, 2 | 8 | intercambiar 7 y 2 para eliminar 7 del montón | |
2, 6, 3, 4, 5, 1, 7 | 7 | 8 | eliminar 7 del montón y agregar a la matriz ordenada | |
2 , 6 , 3, 4, 5, 1 | 2, 6 | 7, 8 | intercambia 2 y 6 ya que no están en orden en el montón | |
6, 2 , 3, 4, 5 , 1 | 2, 5 | 7, 8 | intercambia 2 y 5 ya que no están en orden en el montón | |
6 , 5, 3, 4, 2, 1 | 6, 1 | 7, 8 | intercambiar 6 y 1 para eliminar 6 del montón | |
1, 5, 3, 4, 2, 6 | 6 | 7, 8 | eliminar 6 del montón y agregar a la matriz ordenada | |
1 , 5 , 3, 4, 2 | 15 | 6, 7, 8 | intercambie 1 y 5 ya que no están en orden en el montón | |
5, 1 , 3, 4 , 2 | 1, 4 | 6, 7, 8 | intercambie 1 y 4 ya que no están en orden en el montón | |
5 , 4, 3, 1, 2 | 5, 2 | 6, 7, 8 | intercambiar 5 y 2 para eliminar 5 del montón | |
2, 4, 3, 1, 5 | 5 | 6, 7, 8 | eliminar 5 del montón y agregar a la matriz ordenada | |
2 , 4 , 3, 1 | 2, 4 | 5, 6, 7, 8 | intercambia 2 y 4 ya que no están en orden en el montón | |
4 , 2, 3, 1 | 4, 1 | 5, 6, 7, 8 | intercambiar 4 y 1 para eliminar 4 del montón | |
1, 2, 3, 4 | 4 | 5, 6, 7, 8 | eliminar 4 del montón y agregar a la matriz ordenada | |
1 , 2, 3 | 1, 3 | 4, 5, 6, 7, 8 | intercambie 1 y 3 ya que no están en orden en el montón | |
3 , 2, 1 | 3, 1 | 4, 5, 6, 7, 8 | intercambiar 3 y 1 para eliminar 3 del montón | |
1, 2, 3 | 3 | 4, 5, 6, 7, 8 | eliminar 3 del montón y agregar a la matriz ordenada | |
1 , 2 | 1, 2 | 3, 4, 5, 6, 7, 8 | intercambiar 1 y 2 ya que no están en orden en el montón | |
2 , 1 | 2, 1 | 3, 4, 5, 6, 7, 8 | intercambiar 2 y 1 para eliminar 2 del montón | |
1, 2 | 2 | 3, 4, 5, 6, 7, 8 | eliminar 2 del montón y agregar a la matriz ordenada | |
1 | 1 | 2, 3, 4, 5, 6, 7, 8 | eliminar 1 del montón y agregar a la matriz ordenada | |
1, 2, 3, 4, 5, 6, 7, 8 | terminado |
Notas
- ^ Skiena, Steven (2008). "Búsqueda y clasificación". El Manual de diseño de algoritmos . Saltador. pag. 109. doi : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.
[H] eapsort no es más que una implementación de ordenación por selección utilizando la estructura de datos correcta.
- ↑ Williams, 1964
- ^ a b Latón, Peter (2008). Estructuras de datos avanzadas . Prensa de la Universidad de Cambridge. pag. 209. ISBN 978-0-521-88037-4.
- ^ "Colas de prioridad" . Archivado desde el original el 9 de septiembre de 2020 . Consultado el 10 de septiembre de 2020 .
- ^ Suchenek, Marek A. (2012), "Análisis elemental pero preciso del peor de los casos del programa de construcción de pilas de Floyd", Fundamenta Informaticae , 120 (1): 75–92, doi : 10.3233 / FI-2012-751
- ^ a b c LaMarca, Anthony; Ladner, Richard E. (abril de 1999). "La influencia de los cachés en el rendimiento de la clasificación" . Revista de algoritmos . 31 (1): 66–104. CiteSeerX 10.1.1.456.3616 . doi : 10.1006 / jagm.1998.0985 . S2CID 206567217 .Ver particularmente la figura 9c en la p. 98.
- ^ a b Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). "Estudio de caso de ingeniería de rendimiento: construcción de pilas" (PostScript) . Revista ACM de algoritmos experimentales . 5 (15): 15 – es. CiteSeerX 10.1.1.35.3248 . doi : 10.1145 / 351827.384257 . S2CID 30995934 . Fuente de PDF alternativa .
- ^ Chen, Jingsen; Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (27 a 31 de agosto de 2012). Construcción de montón in situ con comparaciones, movimientos y errores de caché optimizados (PDF) . 37º congreso internacional sobre fundamentos matemáticos de la informática. Bratislava, Eslovaquia. págs. 259-270. doi : 10.1007 / 978-3-642-32589-2_25 . ISBN 978-3-642-32588-5. S2CID 1462216 . Archivado desde el original (PDF) el 29 de diciembre de 2016. Ver particularmente la Fig.3.
- ^ a b c Wegener, Ingo (13 de septiembre de 1993). " BOTTOM-UP HEAPSORT , una nueva variante de HEAPSORT que supera , en promedio, QUICKSORT (si n no es muy pequeño)" (PDF) . Informática Teórica . 118 (1): 81–98. doi : 10.1016 / 0304-3975 (93) 90364-y .Aunque se trata de una reimpresión de un trabajo publicado por primera vez en 1990 (en la conferencia Mathematical Foundations of Computer Science), la técnica fue publicada por Carlsson en 1987. [15]
- ^ a b c Fleischer, Rudolf (febrero de 1994). "Un límite inferior ajustado para el peor de los casos de ordenación de pila de abajo hacia arriba" (PDF) . Algoritmica . 11 (2): 104-115. doi : 10.1007 / bf01182770 . hdl : 11858 / 00-001M-0000-0014-7B02-C . S2CID 21075180 . También disponible como Fleischer, Rudolf (abril de 1991). Un límite inferior ajustado para el peor de los casos de ordenación de pila de abajo hacia arriba (PDF) (informe técnico). MPI-INF . MPI-I-91-104.
- ^ a b Mehlhorn, Kurt ; Sanders, Peter (2008). "Colas de prioridad" (PDF) . Algoritmos y estructuras de datos: la caja de herramientas básica . Saltador. pag. 142. ISBN 978-3-540-77977-3.
- ^ a b McDiarmid, CJH; Reed, BA (septiembre de 1989). "Construyendo montones rápidamente" (PDF) . Revista de algoritmos . 10 (3): 352–365. doi : 10.1016 / 0196-6774 (89) 90033-3 .
- ^ a b MacKay, David JC (diciembre de 2005). "Heapsort, Quicksort y Entropía" . Consultado el 12 de febrero de 2021 .
- ^ Moret, Bernard ; Shapiro, Henry D. (1991). "8.6 Heapsort". Algoritmos de P a NP Volumen 1: Diseño y Eficiencia . Benjamin / Cummings. pag. 528. ISBN 0-8053-8008-6.
A falta de un nombre mejor, llamamos a este programa mejorado 'heapsort con rebote. '
- ^ a b Carlsson, Scante (marzo de 1987). "Una variante de heapsort con un número casi óptimo de comparaciones" (PDF) . Cartas de procesamiento de información . 24 (4): 247–250. doi : 10.1016 / 0020-0190 (87) 90142-6 . S2CID 28135103 . Archivado desde el original (PDF) el 27 de diciembre de 2016.
- ^ Wegener, Ingo (marzo de 1992). "La complejidad del peor caso de la variante de McDiarmid y Reed de BOTTOM-UP HEAPSORT es menor que n log n + 1,1 n " . Información y Computación . 97 (1): 86–96. doi : 10.1016 / 0890-5401 (92) 90005-Z .
- ^ Tenenbaum, Aaron M .; Augenstein, Moshe J. (1981). "Capítulo 8: Clasificación". Estructuras de datos usando Pascal . pag. 405. ISBN 0-13-196501-8.
Escriba una rutina de clasificación similar al heapsort, excepto que utiliza un montón ternario.
- ^ Cantone, Domenico; Concotti, Gianluca (1º a 3 de marzo de 2000). QuickHeapsort, una combinación eficiente de algoritmos de clasificación clásicos . 4ª Conferencia Italiana sobre Algoritmos y Complejidad. Apuntes de conferencias en Ciencias de la Computación. 1767 . Roma. págs. 150-162. ISBN 3-540-67159-5.
- ^ Cantone, Domenico; Concotti, Gianluca (agosto de 2002). "QuickHeapsort, una combinación eficiente de algoritmos de clasificación clásicos" (PDF) . Informática Teórica . 285 (1): 25–42. doi : 10.1016 / S0304-3975 (01) 00288-2 . Zbl 1016.68042 .
- ^ Diekert, Volker; Weiß, Armin (agosto de 2016). "QuickHeapsort: modificaciones y análisis mejorado". Teoría de los sistemas informáticos . 59 (2): 209–230. arXiv : 1209,4214 . doi : 10.1007 / s00224-015-9656-y .
- ^ Dijkstra, Edsger W. Smoothsort: una alternativa a la clasificación in situ (EWD-796a) (PDF) . Archivo EW Dijkstra. Centro de Historia Estadounidense, Universidad de Texas en Austin .( transcripción )
- ^ Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort — Adapted for Presorted Files", WADS '89: Proceedings of the Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science, 382 , Londres, Reino Unido: Springer-Verlag, págs. 499– 509, doi : 10.1007 / 3-540-51542-9_41 , ISBN 978-3-540-51542-5 Heapsort: adaptado para archivos preordenados (Q56049336) .
- ^ Schwartz, Keith (27 de diciembre de 2010). "CartesianTreeSort.hh" . Archivo de código interesante . Consultado el 5 de marzo de 2019 .
- ^ Katajainen, Jyrki (23 de septiembre de 2013). Buscando la mejor cola de prioridad: lecciones aprendidas . Ingeniería de algoritmos (Seminario 13391). Dagstuhl. págs. 19-20, 24.
- ^ Katajainen, Jyrki (2 a 3 de febrero de 1998). The Ultimate Heapsort . Computación: el 4º Simposio de Teoría de Australasia. Comunicaciones de informática de Australia . 20 (3). Perth. págs. 87–96.
- ^ Morris, John (1998). "Comparación de ordenaciones rápidas y de montón" . Estructuras de datos y algoritmos (notas de clase). Universidad de Australia Occidental . Consultado el 12 de febrero de 2021 .
- ^ https://github.com/torvalds/linux/blob/master/lib/sort.c Fuente del kernel de Linux
- ^ Maus, Arne (14 de mayo de 2014). "Clasificación generando la permutación de clasificación y el efecto del almacenamiento en caché en la clasificación" .Consulte la Fig. 1 en la p. 6.
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