Ordenación por montones

A continuación se muestra una forma sencilla de implementar el algoritmo en pseudocódigo . Los arreglos están indexados desde cero y swapse utiliza para intercambiar dos elementos del arreglo. El movimiento "hacia abajo" significa desde la raíz hacia las hojas, o desde índices más bajos a más altos. Nótese que durante la ordenación, el elemento más grande se encuentra en la raíz del montón en a[0], mientras que al final de la ordenación, el elemento más grande se encuentra en a[end].

El procedimiento heapsort(a, count) recibe como entrada: un arreglo no ordenado a de longitud count.(Construye el montón en el array a de manera que el valor más grande esté en la raíz) amontonar(a, count) (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 que lo precede, es decir, a[end:count−1] está ordenado.) fin ← recuento mientras end > 1 hacer (el tamaño del montón se reduce en uno) fin ← fin − 1 (a[0] es la raíz y el valor más grande. El intercambio lo mueve delante de los elementos ordenados.) intercambio(a[fin], a[0]) (el intercambio arruinó la propiedad del montón, así que restáurela) siftDown(a, 0, end)

La rutina de ordenación utiliza dos subrutinas, heapifyy siftDown. La primera es la rutina común de construcción de montón in situ, mientras que la segunda es una subrutina común para implementar heapify.

(Coloca los elementos de 'a' en orden de montón, in situ) procedimiento heapify(a, count) es (start se inicializa en el primer nodo hoja) (el último elemento en un array basado en 0 está en el índice count-1; encuentra el padre de ese elemento) inicio ← iParent(count-1) + 1 mientras inicio > 0 hacer (ir al último nodo que no sea de montón) inicio ← inicio − 1 (desplazar el nodo en el índice 'start' al lugar adecuado de manera que todos los nodos por debajo del índice 'start' estén en orden de montón) siftDown(a, inicio, conteo) (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 'start', suponiendo que los montones con raíz en sus hijos son válidos) procedimiento siftDown(a, raíz, fin) es mientras iLeftChild(raíz) < fin hacer (Mientras la raíz tenga al menos un hijo) hijo ← iLeftChild(raíz) (Hijo izquierdo de la raíz) (Si hay un hijo derecho 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 intercambio(a[raíz], a[hijo]) raíz ← hijo (repetir para continuar filtrando hacia abajo el hijo ahora) de lo contrario (La raíz contiene el elemento más grande. Dado que podemos asumir que los montones con raíz en los hijos son válidos, esto significa que hemos terminado.) retornar

El heapifyprocedimiento consiste en construir pequeños montículos y fusionarlos repetidamente siftDown. Comienza con las hojas, observando que son montículos triviales pero válidos por sí mismos, y luego agrega los padres. A partir del elemento n /2 y retrocediendo, cada nodo interno se convierte en la raíz de un montículo válido mediante un proceso de filtrado descendente. El último paso consiste en filtrar el primer elemento, tras lo cual todo el arreglo cumple con la propiedad de montículo.

Para comprobar que esto requiere un tiempo O ( n ) , cuente el número de iteraciones en el peor de los casos siftDown. La última mitad del arreglo requiere cero iteraciones, el cuarto anterior requiere como máximo una iteración, el octavo anterior requiere como máximo dos iteraciones, el decimosexto anterior requiere como máximo tres, y así sucesivamente.

Visto de otra manera, si asumimos que cada siftDownllamada requiere el número máximo de iteraciones, la primera mitad del array requiere una iteración, el primer cuarto requiere una más (un total de 2), el primer octavo requiere otra más (un total de 3), y así sucesivamente.

Esto suma 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 ₂ ( n ) − e ₂ ( n ) , donde s ₂ ( n ) es el número de bits 1 en la representación binaria de n y e ₂ ( n ) es el número de bits 0 finales . ^{[ 6 ] [ 7 ]}

Aunque es conveniente pensar en las dos fases por separado, la mayoría de las implementaciones las combinan, 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 porción del arreglo antes startde no está ordenada, mientras que la porción 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 el arreglo está completamente ordenado.

El procedimiento heapsort(a, count) recibe como entrada: un arreglo no ordenado a de longitud count. inicio ← piso(conteo/2) fin ← recuento mientras fin > 1 hacer si inicio > 0 entonces (construcción de montón) inicio ← inicio − 1 de lo contrario (extracción de montón) fin ← fin − 1 intercambio(a[fin], a[0]) (Lo siguiente es siftDown(a, inicio, fin)) raíz ← inicio mientras iLeftChild(root) < fin hacer hijo ← iLeftChild(raíz) (Si hay un hijo derecho 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 intercambio(a[raíz], a[hijo]) raíz ← hijo (repetir para seguir filtrando hacia abajo el hijo ahora) de lo contrario salir (volver al bucle exterior)

La descripción anterior utiliza el algoritmo de construcción de montículos mejorado de Floyd, que opera en tiempo O ( n ) y utiliza la misma siftDownprimitiva que la fase de extracción del montículo. Si bien este algoritmo, al ser más rápido y sencillo de programar, es utilizado por todas las implementaciones prácticas de ordenación por montículos, el algoritmo original de Williams puede ser más fácil de entender y es necesario para implementar una cola de prioridad de montículos binarios más general .

En lugar de fusionar muchos montículos pequeños, el algoritmo de Williams mantiene un único montículo al principio del array y añade repetidamente un elemento adicional mediante una siftUpprimitiva. Al estar al final del array, el nuevo elemento es una hoja y no tiene hijos de los que preocuparse, pero puede violar la propiedad de montículo al ser mayor que su padre. En este caso, se intercambia con su padre y se repite la prueba hasta que el padre sea mayor o no haya padre (se ha llegado a la raíz). En pseudocódigo, esto es:

El procedimiento siftUp(a, end) es la entrada: a es el array, que está ordenado por montículo hasta end-1. end es el nodo a clasificar. mientras end > 0 padre := iParent(fin) Si a[padre] < a[fin] entonces (fuera del orden de montículo máximo) intercambio(a[padre], a[fin]) fin := padre (continuar filtrando hacia arriba) de lo contrario devolverEl procedimiento heapify(a, count) es (comenzar con un montón trivial de un solo elemento) fin := 1 mientras end < count (desplazar el nodo en el índice end al lugar adecuado de manera que todos los nodos por encima del índice end estén en orden de montón) siftUp(a, fin) fin := fin + 1 (después de filtrar el último nodo, todos los nodos están en orden de montón)

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 siftDownlas operaciones se aplican a montones muy pequeños . La mitad de los montones son montones triviales de altura 1 y pueden omitirse por completo, la mitad de los restantes son de altura 2, y así sucesivamente. Solo dos llamadas se realizan en montones de tamaño n /2 , y solo una siftDownoperación se realiza en el montón completo de nsiftDown elementos. La operación promedio general tarda O (1) tiempo.

En contraste, en el algoritmo de Williams la mayoría de las llamadas 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 caso: cada nodo agregado se tamiza hasta la raíz, por lo que la llamada promedio siftUprequerirá aproximadamente (log ₂ n − 1)/2 + (log ₂ n − 2)/4 + (log ₂ n − 3)/8 + ⋯ = log ₂ n − (1 + 1/2 + 1/4 + ⋯) = log ₂ n − 2 iteraciones.

Debido a que está dominado por la segunda fase de extracción de montículos, el algoritmo heapsort en sí tiene una complejidad temporal de O ( n log n ) utilizando cualquiera de las versiones de heapify.

El ordenamiento por montículos ascendente es una variante que reduce significativamente el número de comparaciones necesarias. Mientras que el ordenamiento por montículos descendente ordinario requiere 2 n log ₂ n + O ( n ) comparaciones en el peor de los casos y en promedio, ^{[ 10 ]} la variante ascendente requiere n log ₂ n + O (1) comparaciones en promedio, ^{[ 10 ]} y 1,5 n log ₂ n + O ( n ) en el peor de los casos. ^{[ 11 ]}

Si las comparaciones son sencillas (por ejemplo, con claves enteras), la diferencia es irrelevante ^{[ 12 ],} ya que el ordenamiento por montículos 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, el ordenamiento por montículos ascendente resulta ventajoso.

Esto se logra utilizando 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 ordenamiento por montículos descendente, 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 proviene del nivel más bajo del montón, lo que significa que es uno de los elementos más pequeños en el montón, por lo que el tamizado hacia abajo probablemente tomará muchos pasos para moverlo de nuevo hacia abajo. ^{[ 14 ]} En el ordenamiento por montículos descendente, cada paso de siftDownrequiere dos comparaciones, para encontrar el mínimo de tres elementos: el nuevo nodo y sus dos hijos.

El algoritmo de ordenación por montículos de abajo hacia arriba conceptualmente reemplaza la raíz con un valor de −∞ y la desplaza hacia abajo utilizando 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 la desplaza hacia arriba (nuevamente, utilizando una comparación por nivel) hasta que se encuentra la posición correcta.

Esto sitúa la raíz en la misma ubicación que en el método descendente siftDown, pero se requieren menos comparaciones para encontrar esa ubicación. Para cualquier siftDownoperación individual, la técnica ascendente es ventajosa si el número de movimientos descendentes es al menos 2/3 de la altura del árbol (cuando el número de comparaciones es 4/3 veces la altura para cualquiera de las técnicas), y resulta que esto es más que cierto en promedio, incluso para las peores entradas. ^{[ 11 ]}

Una implementación ingenua de este algoritmo conceptual provocaría una copia de datos redundante, ya que la parte ascendente deshace parte de la descendente. Una implementación práctica busca hacia abajo una hoja donde se colocaría −∞, y luego hacia arriba donde debería colocarse la raíz. Finalmente, el recorrido ascendente continúa hasta la posición inicial de la raíz, sin realizar más comparaciones, sino intercambiando nodos para completar la reorganización necesaria. Esta forma optimizada realiza el mismo número de intercambios que la descendente siftDown.

Debido a que llega hasta el fondo y luego vuelve a subir, algunos autores lo llaman ordenamiento por montículos con rebote . ^{[ 15 ]}

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

El valor de retorno leafSearchse utiliza en la siftDownrutina modificada: ^{[ 11 ]}

El procedimiento siftDown(a, i, end) es j ← leafSearch(a, i, end) mientras a[i] > a[j] hacer j ← iParent(j) mientras j > yo hago intercambio(a[i], a[j]) j ← iParent(j)

Se anunció que el algoritmo de ordenación por montículos de abajo hacia arriba superaba al algoritmo de ordenación rápida (con selección de pivote mediana de tres) en matrices de tamaño ≥16000. ^{[ 10 ]}

Una reevaluación de este algoritmo en 2008 demostró que no era más rápido que el ordenamiento por montículos descendente para claves enteras, presumiblemente porque la predicción de ramificaciones moderna anula el costo de las comparaciones predecibles que el ordenamiento por montículos ascendente 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 ₂ ( n +1) + log ₂ log ₂ ( n +1) + 1.82) + O (log ₂ n ) comparaciones, aproximándose al límite inferior teórico de la información de n log ₂ 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: izquierda, derecha y desconocido) ^{[ 13 ]} utiliza menos de n log ₂ n + 1.1 n comparaciones. ^{[ 17 ]}

• El algoritmo de ordenación por montículos ternario utiliza un montículo ternario en lugar de uno binario; es decir, cada elemento del montículo tiene tres hijos. Es más complejo 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 sift-down en un montículo ternario requiere tres comparaciones y un intercambio, mientras que en un montículo binario se requieren dos comparaciones y un intercambio. Dos niveles en un montículo ternario cubren 3 ² = 9 elementos, realizando más trabajo con seis comparaciones que tres niveles en el montículo binario, que solo cubren 2 ³ = 8. Esto es principalmente de interés académico, o como ejercicio para estudiantes, ^{[ 18 ]} ya que la complejidad adicional no justifica el pequeño ahorro, y la ordenación por montículos de abajo hacia arriba supera a ambas.
• El algoritmo de ordenación por montículos optimizado para memoria ^{[ 19 ] : 87} mejora la localidad de referencia de la ordenación por montículos al aumentar aún más el número de hijos. Esto incrementa el número de comparaciones, pero debido a que todos los hijos 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ículo, lo que supone una mejora neta del rendimiento.
• La implementación estándar del algoritmo de construcción de montículos de Floyd provoca un gran número de fallos de caché una vez que el tamaño de los datos supera el de la caché de la CPU . ^{[ 19 ] : 87} Se puede obtener un mejor rendimiento en conjuntos de datos grandes fusionando en orden de profundidad , combinando submontículos lo antes posible, en lugar de combinar todos los submontículos de un nivel antes de pasar al superior. ^{[ 9 ] [ 20 ]}
• El heapsort fuera de lugar ^{[ 21 ] [ 22 ] [ 14 ]} mejora el heapsort de abajo hacia arriba al eliminar el peor caso, garantizando n log ₂ n + O ( n ) comparaciones. Cuando se toma el máximo, en lugar de llenar el espacio desocupado con un valor de datos no ordenado, se llena con un valor centinela −∞ , que nunca "rebota" hacia arriba. Resulta que esto puede usarse como una primitiva en un algoritmo "QuickHeapsort" in situ (y no recursivo). ^{[ 23 ]} Primero, se realiza un paso de partición similar a quicksort, pero invirtiendo el orden de los datos particionados en el arreglo. 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 del arreglo, pero nuestro paso de partición invertido la coloca al principio. Crea un montón a partir de la partición más pequeña y realiza una ordenación por montículos fuera de lugar sobre él, intercambiando los máximos extraídos con valores del final del array. Estos son menores que el pivote, es decir, menores que cualquier valor en el montón, por lo que sirven como valores centinela de −∞ . Una vez completada la ordenación por montículos (y movido el pivote justo antes del final del array ahora ordenado), el orden de las particiones se ha invertido y la partición más grande al principio del array se puede ordenar de la misma manera. (Como no hay recursión no de cola , esto también elimina el uso de pila O (log n ) de quicksort ).
• El algoritmo smoothsort ^{[ 24 ]} es una variación de heapsort desarrollado por Edsger W. Dijkstra en 1981. Al igual que heapsort, el límite superior de smoothsort es O ( n log n ) . La ventaja de smoothsort es que se aproxima a un tiempo de O ( n ) si la entrada ya está ordenada en cierto grado , mientras que heapsort tiene un promedio de O ( n log n ) independientemente del estado de ordenación inicial. Debido a su complejidad, smoothsort se usa con poca frecuencia.
• Levcopoulos y Petersson ^{[ 25 ]} 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 también son árboles cartesianos, al montón binario. ^{[ 26 ]} Como muestran, si la entrada ya está casi ordenada, los árboles cartesianos estarán muy desequilibrados, con pocos nodos que tengan hijos izquierdo y derecho, lo que hace que el montón binario permanezca pequeño y permite 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 por montículos débil, requieren n log ₂ n + O (n) comparaciones en el peor de los casos, cerca del mínimo teórico, utilizando un bit adicional de estado por nodo. Si bien este bit adicional hace que los algoritmos no sean verdaderamente in situ, si se puede encontrar espacio para él dentro del elemento, estos algoritmos son simples y eficientes, ^{[ 9 ] : 40} pero aún más lentos que los montículos binarios si las comparaciones de claves son lo suficientemente baratas (por ejemplo, claves enteras) como para que un factor constante no importe. ^{[ 27 ]}
• El algoritmo de ordenación por montículos definitivo de Katajainen no requiere almacenamiento adicional, realiza n log ₂ n + O (n) comparaciones y un número similar de movimientos de elementos. ^{[ 28 ]} Sin embargo, es aún más complejo y no se justifica a menos que las comparaciones sean muy costosas.