En lugar de usar una matriz y ordenar elementos de mayor a menor, ¿cómo puedo usar un montón?

Bueno, un montón normalmente se implementa utilizando una matriz, pero no importa.

Lo que está describiendo es exactamente lo que sucede en las etapas finales de Heap Sort, donde realmente ordena la matriz subyacente, en su lugar, utilizando el siguiente algoritmo:

Después de construir un montón mínimo, el valor más pequeño se encuentra en la parte superior del montón, que se encuentra en la parte frontal de la matriz. Entonces, sabiendo que este es el elemento más pequeño del montón / matriz, lo saca del montón y lo empuja hacia la parte posterior de la matriz, donde se ubicará cuando se ordene toda la matriz.

Otro elemento burbujea en el montón y se convierte en el mínimo posterior del resto de la matriz, nuevamente sentado en la parte superior del montón y en la parte frontal de la matriz. Entonces, repites lo que hiciste la última vez: saca la cabeza del montón, cambia el elemento ahora penúltimo en la matriz y luego reconstruye el montón.

Repita este proceso hasta que haya un solo elemento en el montón, en cuyo punto se ordena la matriz subyacente.

En una sola oración: extrae repetidamente los mínimos del montón y los almacena de principio a fin en la matriz.

La estructura de datos del montón es un pseudo-árbol (más sobre esto a continuación) que inserta elementos en lg (n) y elimina el elemento más bajo (o más alto) en el tiempo lg (n). Para ordenar, inserte cada elemento en el montón y luego elimine cada elemento del montón para obtener los datos ordenados.

Un montón se puede implementar como una matriz donde un “nodo” en el índice n tiene dos “hijos” en las indicaciones 2n y 2n + 1. Las inserciones siempre ocurren en el último índice disponible, y son seguidas por un algoritmo de rotación para preservar la regla estipulada anteriormente. Por lo tanto, el índice 0 siempre contiene el elemento más bajo o más alto para un montón mínimo o un montón máximo, respectivamente. Después de la inserción, verifique si su padre es mayor que usted, si es así, cámbielos. Recurrir hasta que ningún padre sea mayor que su hijo.

Para eliminar elementos, devuelva el índice 0 después de extraer el hijo más grande y de forma recursiva hacia arriba su hijo más grande.

Heapsort (descrito en el primer párrafo) tiene una complejidad de peor caso de n lg (n), pero tiende a ser más lento que un quicksort bien implementado. Al igual que Quicksort, se puede hacer en su lugar pero es inestable.