stringtranslate.com

Ordenamiento por montículos

En informática , el heapsort es un algoritmo de ordenamiento basado en comparación que puede considerarse como "una implementación del ordenamiento por selección utilizando la estructura de datos correcta ". [3] Al igual que el ordenamiento por selección, el 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 del ordenamiento por selección, el heapsort no pierde tiempo con un escaneo de tiempo lineal de la región sin ordenar; en cambio, el heapsort mantiene la región sin ordenar en una estructura de datos de montón para encontrar de manera eficiente 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 un quicksort bien implementado , 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 quicksort del mundo real incluyen una implementación de heapsort como respaldo en caso de que detecten que quicksort se está degenerando. Heapsort es un algoritmo in situ , pero no es un ordenamiento estable .

JWJ Williams inventó el algoritmo Heapsort 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 en el lugar, continuando su investigación anterior sobre el algoritmo treesort . [5]

Descripción general

El algoritmo de ordenació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á de la matriz de objetos que se van a ordenar; la matriz se interpreta como un árbol binario completo donde cada elemento de la matriz es un nodo y los vínculos padre e hijo de cada nodo se definen mediante aritmética simple en los índices de la matriz. Para una matriz basada en cero, el nodo raíz se almacena en el índice 0 y los nodos vinculados al nodo ison

 iHijoIzquierdo(i) = 2⋅i + 1 iHijoDerecho(i) = 2⋅i + 2 iParent(i) = piso((i−1) / 2)

donde la función floor redondea hacia abajo hasta el entero anterior. Para una explicación más detallada, consulte Heap binario § Implementación de heap .

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 (ver Montón binario § Construcción de 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 ordenación por montículos se realiza normalmente en el lugar. Durante la primera fase, la matriz se divide en un prefijo sin ordenar y un sufijo ordenado por montículos (inicialmente vacío). Cada paso reduce el prefijo y expande el sufijo. Cuando el prefijo está vacío, esta fase está completa. Durante la segunda fase, la matriz se divide en un prefijo ordenado por montículos 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.

Algoritmo

El algoritmo de ordenación por montículos comienza reorganizando la matriz en un montón binario de máximo orden. 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, el montón, que se dañó al reemplazar la raíz, se repara 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:

  1. Llamar a la heapify()función en la matriz. Esto crea un montón a partir de una matriz en O ( n ) operaciones.
  2. Intercambia el primer elemento de la matriz (el elemento más grande del montón) con el último elemento del montón. Disminuye el rango considerado del montón en uno.
  3. Llame a la siftDown()función en la matriz para mover el nuevo primer elemento a su lugar correcto en el montón.
  4. Regrese al paso (2) hasta que la matriz restante sea un solo elemento.

La heapify()operación se ejecuta una vez y tiene un rendimiento de O ( n ) . La siftDown()función se llama n veces y requiere O (log n ) de trabajo cada vez, debido a que su recorrido comienza desde el nodo raíz. Por lo tanto, el rendimiento de este algoritmo es O ( n + n log n ) = O ( n log n ) .

El núcleo del algoritmo es la siftDown()función. Esta 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 la raíz. Esto se hace más fácilmente encontrando el hijo mayor y luego comparándolo con la raíz. Hay tres casos:

  1. Si no hay hijos (los dos montones originales están vacíos), la propiedad del montón se cumple trivialmente y no se requiere ninguna acción adicional.
  2. Si la raíz es mayor o igual que el hijo más grande, la propiedad del montón se mantiene y, de la misma manera, no se requiere ninguna acción adicional.
  3. Si la raíz es menor que el hijo mayor, intercambie los dos nodos. La propiedad de montón ahora se mantiene en el nodo recién promovido (es mayor o igual que ambos hijos y, de hecho, mayor que cualquier descendiente), pero puede ser violada entre el ex-raíz recién degradado y sus nuevos hijos. Para corregir esto, repita la siftDown()operación en el subárbol con raíz en el ex-raíz recién degradado.

El número de iteraciones en cualquier siftdown()llamada está limitado por la altura del árbol, que es ⌊ log 2 n ⌋ = O (log n ) .

Pseudocódigo

La siguiente es una forma sencilla de implementar el algoritmo en pseudocódigo . Las matrices se basan en 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 inferiores a superiores. 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].

El procedimiento heapsort(a, count) se  ingresa como entrada: una matriz desordenada a de longitud count  (Construya el montón en la matriz a de modo que el valor más grande esté en la raíz) heapify(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] está en orden ordenado). fin ← contar mientras que 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 al frente de los elementos ordenados). intercambiar(a[fin], a[0]) (el intercambio arruinó la propiedad del montón, así que restáurelo) tamizar(a, 0, fin)

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

(Coloca los elementos de 'a' en orden de montón, en su lugar) procedimiento heapify(a, count) es  (start se inicializa en el primer nodo de hoja)  (el último elemento en una matriz basada en 0 está en el índice count-1; encuentra el padre de ese elemento) inicio ← iParent(count-1) + 1  mientras start > 0 do  (ir al último nodo que no pertenece al montón) inicio ← inicio − 1 (clasificar el nodo en el índice 'inicio' hasta el lugar apropiado de modo que todos los nodos debajo  del índice de inicio estén en orden de montón) siftDown(a, inicio, recuento) (después de filtrar la raíz, todos los nodos/elementos están en orden de montón) (Reparar el montón cuyo elemento raíz está en el índice 'inicio', asumiendo que los montones enraizados en sus hijos son válidos) procedimiento siftDown(a, root, end) es  while iLeftChild(root) < end do  (Mientras la raíz tenga al menos un hijo) child ← iLeftChild(root) (Hijo izquierdo de la raíz)  (Si hay un hijo derecho y ese hijo es mayor)  if child+1 < end and a[child] < a[child+1] then niño ← niño + 1  si a[raíz] < a[hijo] entonces swap(a[raíz], a[hijo]) raíz ← hijo (repetir para continuar seleccionando el hijo ahora)  de lo contrario  (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 funciona creando 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 mediante el tamizado descendente. El último paso es tamizar el primer elemento, después de lo cual toda la matriz obedece la propiedad del montón.

Para ver que esto lleva un tiempo de O ( n ) , cuente el número de iteraciones en el peor de los casos siftDown. La última mitad de la matriz requiere cero iteraciones, el cuarto anterior requiere como máximo una iteración, la octava anterior requiere como máximo dos iteraciones, la decimosexta 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 (total 2), el primer octavo requiere otra más (total 3), y así sucesivamente.

Esto da como resultado 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 lo 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 bits 1 en la representación binaria de n y e 2 ( n ) es el número de bits 0 finales . [6] [7]

Implementación estándar

Aunque es conveniente pensar en las dos fases por separado, la mayoría de las implementaciones combinan las dos, lo que permite que una sola instancia de siftDownse expanda en línea . [8] : Algoritmo H  Dos variables (aquí, starty end) mantienen un registro 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.

El procedimiento heapsort(a, count) se  ingresa como entrada: una matriz desordenada a de longitud count  inicio ← piso(cuenta/2) fin ← contar mientras fin > 1 hacer  si inicio > 0 entonces  (construcción del montón) inicio ← inicio − 1 De lo contrario  (Extracción del montón) fin ← fin − 1 intercambiar(a[fin], a[0])  (Lo siguiente es siftDown(a, inicio, fin)) raíz ← inicio mientras iLeftChild(root) < fin hacer niño ← iLeftChild(raíz) (Si hay un hijo correcto y ese hijo es mayor)  si hijo+1 < fin y a[hijo] < a[hijo+1] entonces niño ← niño + 1  si a[raíz] < a[hijo] entonces swap(a[raíz], a[hijo]) raíz ← hijo (repetir para continuar filtrando al hijo ahora)  de lo contrario  romper  (regresar al bucle externo)

Variaciones

Construcción del montón de Williams

La descripción anterior utiliza el algoritmo de construcción de montón mejorado 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 simple de programar, se utiliza en todas las implementaciones prácticas de heapsort, 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 principio de la matriz y añade repetidamente un elemento adicional utilizando un siftUpprimitivo. 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, intercámbielo con su padre y repita la prueba hasta que el padre sea mayor o no haya padre (hemos llegado a la raíz). En pseudocódigo, esto es:

 procedimiento siftUp(a, end) es  la entrada:  a es la matriz, que se ordena en montón hasta end-1.  end es el nodo que se va a cribar.  mientras end > 0 padre := iParent(fin) si a[padre] < a[fin] entonces  (fuera del orden de montón máximo) swap(a[padre], a[fin]) fin := padre (continuar seleccionando)  de lo contrario  regresar  procedimiento heapify(a, count) es  (comienza con un montón trivial de un solo elemento) fin := 1  mientras que fin < recuento (seleccione el nodo en el índice fin hasta el lugar apropiado de modo que  todos los nodos por encima del índice fin estén en orden de montón) tamizar(a, fin) fin := fin + 1 (después de seleccionar el último nodo, todos los nodos están en orden de montón)
Diferencia en la complejidad temporal entre la versión "siftDown" y la versión "siftUp".

Para entender por qué este algoritmo puede tardar asintóticamente más tiempo en construir un montón ( O ( n log n ) frente a 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 de altura 2, y así sucesivamente. Solo dos llamadas son 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, en 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, 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 preordenadas causarán el peor de los casos: cada nodo agregado se tamiza hasta la raíz, por lo que la llamada promedio a siftUprequerirá aproximadamente (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 heapsort en sí tiene una complejidad de tiempo O ( n log n ) utilizando cualquiera de las versiones de heapify.

Ordenación por montículos de abajo a arriba

El método bottom-up heapsort es una variante que reduce el número de comparaciones requeridas en un factor significativo. Mientras que el método "top-down" heapsort común requiere 2 n log 2 n + O ( n ) comparaciones en el peor de los casos y en promedio, [10] la variante bottom-up 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 ordenación descendente compara valores que ya se han cargado desde la memoria. Sin embargo, si las comparaciones requieren una llamada a una función u otra lógica compleja, entonces la ordenación ascendente resulta ventajosa.

Esto se logra mediante un siftDownprocedimiento más elaborado. El cambio mejora ligeramente la fase de construcción del montón en tiempo lineal, [13] pero es más significativo en la segunda fase. Al igual que en el heapsort 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 con a[end], luego tamiza este último elemento hacia abajo en el montón. Pero este elemento vino 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 el tamizado probablemente tomará muchos pasos para moverlo hacia abajo. [14] En el heapsort de arriba hacia abajo, cada paso de siftDownrequiere dos comparaciones, para encontrar el mínimo de tres elementos: el nuevo nodo y sus dos hijos.

El método bottom-up heapsort reemplaza conceptualmente la raíz con un valor de −∞ y lo filtra hacia abajo usando solo una comparación por nivel (ya que ningún hijo puede ser menor que −∞) hasta que se alcanzan las hojas, luego reemplaza el −∞ con el valor correcto y lo filtra hacia arriba (nuevamente, usando una comparación por nivel) hasta que se encuentra la posición correcta.

Esto coloca la raíz en la misma ubicación que la técnica de arriba hacia abajo siftDown, pero se requieren menos comparaciones para encontrar esa ubicación. Para cualquier siftDownoperación individual, 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 caso. [11]

Una implementación ingenua de este algoritmo conceptual provocaría una copia redundante de datos, ya que la parte de cribado hacia arriba deshace parte del cribado hacia abajo. 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 hacia arriba continúa hasta la posición inicial de la raíz, sin realizar más comparaciones, sino intercambiando nodos para completar la reorganización necesaria. Esta forma optimizada realiza la misma cantidad de intercambios que la de arriba hacia abajo siftDown.

Debido a que llega hasta el fondo y luego vuelve a subir, algunos autores lo denominan "heapsort" con rebote . [15]

La función leafSearch(a, i, fin) es j ← yo mientras iRightChild(j) < end do  (Determinar cuál de los dos hijos de j es el mayor)  si a[iRightChild(j)] > a[iLeftChild(j)] entonces j ← iHijoDerecho(j) demás j ← iHijoIzquierdo(j) (En el último nivel, puede haber solo un hijo)  si iLeftChild(j) < end entonces j ← iHijoIzquierdo(j) volver j

El valor de retorno de se utiliza en la rutina leafSearchmodificada : [11]siftDown

El procedimiento siftDown(a, i, fin) es j ← leafSearch(a, i, fin) mientras que a[i] > a[j] lo hace j ← iPadre(j) mientras j > yo hago intercambiar(a[i], a[j]) j ← iPadre(j)

Se anunció que el ordenamiento por montículos de abajo hacia arriba superaba al ordenamiento rápido (con selección de pivote de 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 el heapsort de arriba hacia abajo para claves enteras, presumiblemente porque la predicción de bifurcaciones moderna anula el costo de las comparaciones predecibles que el heapsort 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 caso de ( 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. [16]

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] utiliza menos de n log 2 n + 1,1 n comparaciones. [17]

Otras variaciones

Comparación con otros tipos

Heapsort compite principalmente con quicksort , otro algoritmo de ordenamiento basado en comparación inestable, de uso general y muy eficiente.

Las principales ventajas de Heapsort son su código simple y no recursivo , el requisito mínimo de almacenamiento auxiliar y un rendimiento confiablemente bueno: 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 ordenamientos por comparación . Si bien no puede hacerlo mejor que O ( n log n ) para entradas preordenadas, tampoco sufre del peor caso de quicksort O ( n 2 ) .

Las implementaciones de quicksort en el 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 introsort y quicksort que anula patrones [29] utilizan heapsort como último recurso si detectan un comportamiento degenerado. 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 son mayormente aleatorios, y no hay una manera sencilla de convertirlo en un algoritmo paralelo .

Las garantías de rendimiento en el peor de los casos hacen que heapsort sea popular en la computación 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 confiablemente "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 administración de bases de datos probablemente querría un algoritmo de clasificación optimizado de manera más agresiva.

Un quicksort bien implementado es generalmente 2-3 veces más rápido que el heapsort. [19] [32] Aunque el quicksort requiere menos comparaciones, este es un factor menor. (Los resultados que afirman el doble de comparaciones miden la versión de arriba hacia abajo; consulte § Bottom-up heapsort.) La principal ventaja del quicksort 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, el quicksort también se puede implementar en código mayoritariamente libre de ramificaciones , [33] [34] y se pueden usar múltiples CPU para ordenar subparticiones en paralelo. Por lo tanto, se prefiere el quicksort cuando el rendimiento adicional justifica el esfuerzo de implementación.

El otro algoritmo de ordenamiento O ( n log n ) principal es el ordenamiento por combinación , pero rara vez compite directamente con el ordenamiento por montículos porque no se realiza en el lugar. El requisito del ordenamiento por combinación de Ω( n ) de espacio adicional (aproximadamente la mitad del tamaño de la entrada) suele ser prohibitivo, excepto en las situaciones en las que el ordenamiento por combinación tiene una clara ventaja:

Ejemplo

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 . Normalmente hay dos cuando se realiza un cribado ascendente y tres cuando se realiza un cribado descendente, aunque puede haber menos cuando se alcanza la parte superior o inferior del árbol.

Construcción de montículos (algoritmo de Williams)

Un ejemplo de ordenación de montículos utilizando el algoritmo de construcción de montículos de Williams.

Construcción de montículos (algoritmo de Floyd)

Extracción de montón

Notas

  1. ^ Bollobás, B.; Fenner, TI; Frieze, AM (1996). "Sobre el mejor caso de Heapsort" (PDF) . Journal of Algorithms . 20 (11): 205–217. doi :10.1006/jagm.1996.0011.
  2. ^ Sedgewick, Robert ; Schaffer, Russel W. (octubre de 1990). El mejor caso de Heapsort (informe técnico). Universidad de Princeton. TR-293-90.
  3. ^ Skiena, Steven (2008). "Búsqueda y ordenación". Manual de diseño de algoritmos (3.ª ed.). Springer. pág. 116. doi :10.1007/978-3-030-54256-6_4. ISBN 978-3-030-54255-9El nombre que normalmente se le da a este algoritmo, heapsort , oculta el hecho de que el algoritmo no es nada más que una implementación de ordenamiento por selección que utiliza la estructura de datos correcta.
  4. ^ Williams 1964
  5. ^ ab Brass, Peter (2008). Estructuras de datos avanzadas . Cambridge University Press. pág. 209. ISBN 978-0-521-88037-4.
  6. ^ Suchenek, Marek A. (2012). "Análisis elemental pero preciso del peor caso del programa de construcción de pilas de Floyd". Fundamenta Informaticae . 120 (1): 75–92. doi :10.3233/FI-2012-751.
  7. ^ Suchenek, Marek A. (7 de abril de 2015). "Un análisis completo del peor caso de Heapsort con verificación experimental de sus resultados, un manuscrito". arXiv : 1504.01459 [cs.DS].
  8. ^ Knuth 1997
  9. ^ abc Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). "Estudio de caso de ingeniería de rendimiento: construcción de montículos" (PostScript) . ACM Journal of Experimental Algorithmics . 5 (15): 15–es. CiteSeerX 10.1.1.35.3248 . doi :10.1145/351827.384257. S2CID  30995934. Fuente PDF alternativa.
  10. ^ abc Wegener, Ingo (13 de septiembre de 1993). "BOTTOM-UP HEAPSORT, una nueva variante de HEAPSORT que supera, en promedio, a QUICKSORT (si n no es muy pequeño)" (PDF) . Theoretical Computer Science . 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 Fundamentos matemáticos de la informática), la técnica fue publicada por Carlsson en 1987. [16]
  11. ^ abc Fleischer, Rudolf (febrero de 1994). "Un límite inferior ajustado para el peor caso de Bottom-Up-Heapsort" (PDF) . Algorithmica . 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 caso de Bottom-Up-Heapsort (PDF) (informe técnico). MPI-INF . MPI-I-91-104.
  12. ^ ab Mehlhorn, Kurt ; Sanders, Peter (2008). "Colas de prioridad" (PDF) . Algoritmos y estructuras de datos: la caja de herramientas básica. Springer. p. 142. ISBN 978-3-540-77977-3.
  13. ^ ab McDiarmid, CJH; Reed, BA (septiembre de 1989). "Construcción rápida de montículos" (PDF) . Journal of Algorithms . 10 (3): 352–365. doi :10.1016/0196-6774(89)90033-3.
  14. ^ ab MacKay, David JC (diciembre de 2005). "Heapsort, Quicksort, and Entropy" (Ordenamiento por hendiduras, ordenamiento rápido y entropía) . Consultado el 12 de febrero de 2021 .
  15. ^ Moret, Bernard ; Shapiro, Henry D. (1991). "8.6 Heapsort". Algoritmos de P a NP Volumen 1: Diseño y eficiencia . Benjamin/Cummings. pág. 528. ISBN 0-8053-8008-6A falta de un nombre mejor , llamamos a este programa mejorado 'heapsort con rebote ' .
  16. ^ ab Carlsson, Scante (marzo de 1987). "Una variante de heapsort con un número casi óptimo de comparaciones" (PDF) . Information Processing Letters . 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.
  17. ^ 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,1n". Información y computación . 97 (1): 86–96. doi : 10.1016/0890-5401(92)90005-Z .
  18. ^ Tenenbaum, Aaron M.; Augenstein, Moshe J. (1981). "Capítulo 8: Ordenación". Estructuras de datos con Pascal . Prentice-Hall. pág. 405. ISBN 0-13-196501-8. Escriba una rutina de clasificación similar a heapsort excepto que utiliza un montón ternario.
  19. ^ abc LaMarca, Anthony; Ladner, Richard E. (abril de 1999). "La influencia de los cachés en el rendimiento de la ordenación" (PDF) . Journal of Algorithms . 31 (1): 66–104. CiteSeerX 10.1.1.456.3616 . doi :10.1006/jagm.1998.0985. S2CID  206567217. Véase en particular la figura 9c en la pág. 98.
  20. ^ Chen, Jingsen; Edelkamp, ​​Stefan; Elmasry, Amr; Katajainen, Jyrki (27–31 de agosto de 2012). "Construcción de montículos in situ con comparaciones optimizadas, movimientos y errores de caché" (PDF) . Fundamentos matemáticos de la informática 2012. 37.ª conferencia internacional sobre Fundamentos matemáticos de la informática. Apuntes de clase en informática. Vol. 7464. 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.Véase en particular la figura 3.
  21. ^ Cantone, Domenico; Concotti, Gianluca (1–3 de marzo de 2000). QuickHeapsort, una combinación eficiente de algoritmos de ordenamiento clásicos. 4.ª Conferencia italiana sobre algoritmos y complejidad. Apuntes de clase en informática. Vol. 1767. Roma. pp. 150–162. ISBN 3-540-67159-5.
  22. ^ Cantone, Domenico; Concotti, Gianluca (agosto de 2002). "QuickHeapsort, una combinación eficiente de algoritmos de ordenamiento clásicos" (PDF) . Theoretical Computer Science . 285 (1): 25–42. doi : 10.1016/S0304-3975(01)00288-2 . Zbl  1016.68042.
  23. ^ Diekert, Volker; Weiß, Armin (agosto de 2016). "QuickHeapsort: modificaciones y análisis mejorado". Teoría de sistemas informáticos . 59 (2): 209–230. arXiv : 1209.4214 . doi :10.1007/s00224-015-9656-y. S2CID  792585.
  24. ^ 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)
  25. ^ Levcopoulos, Christos; Petersson, Ola (1989). "Heapsort—Adaptado para archivos preordenados". WADS '89: Actas del taller sobre algoritmos y estructuras de datos . Apuntes de clase en informática. Vol. 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).
  26. ^ Schwartz, Keith (27 de diciembre de 2010). «CartesianTreeSort.hh». Archivo de código interesante . Consultado el 5 de marzo de 2019 .
  27. ^ Katajainen, Jyrki (23 de septiembre de 2013). Buscando la mejor cola de prioridad: lecciones aprendidas. Ingeniería de algoritmos (Seminario 13391). Dagstuhl. pp. 19–20, 24.
  28. ^ Katajainen, Jyrki (2-3 de febrero de 1998). The Ultimate Heapsort. Computing: the 4th Australasian Theory Symposium. Australian Computer Science Communications . Vol. 20, núm. 3. Perth. págs. 87-96.
  29. ^ Peters, Orson RL (9 de junio de 2021). "Ordenamiento rápido que anula patrones". arXiv : 2106.05123 [cs.DS].
    Peters, Orson RL "pdqsort". Github . Consultado el 2 de octubre de 2023 .
  30. ^ Morris, John (1998). "Comparación de ordenamientos rápidos y de montón". Estructuras de datos y algoritmos (apuntes de clase). Universidad de Australia Occidental . Consultado el 12 de febrero de 2021 .
  31. ^ https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/sort.c#n205 Fuente del kernel de Linux
  32. ^ Maus, Arne [en noruego] (14 de mayo de 2014). "Ordenación mediante la generación de la permutación de ordenación y el efecto del almacenamiento en caché en la ordenación".Véase la figura 1 en la página 6.
  33. ^ Edelkamp, ​​Stefan; Weiß, Armin (30 de enero de 2019). "BlockQuicksort: evitar predicciones erróneas de sucursales en Quicksort" (PDF) . Revista de algorítmica experimental . 24 1.4. arXiv : 1604.06697 . doi :10.1145/3274660.
  34. ^ Aumüller, Martin; Hass, Nikolaj (7–8 de enero de 2019). Ordenación rápida y sencilla de bloques mediante el uso del esquema de particionamiento de Lomuto. Vigésimo primer taller sobre ingeniería de algoritmos y experimentos (ALENEX). San Diego. arXiv : 1810.12047 . doi : 10.1137/1.9781611975499.2 .

Referencias

Enlaces externos

La implementación del algoritmo de Wikibook tiene una página sobre el tema: Heapsort