APLICACIÓN EN ORDENACIÓN.

Suponga un array A de N elementos dados. El algoritmo de ordenación por un montón ordenar A consiste en las dos siguientes fases.

Fase A: construir un árbol en montón H con los elementos de A.

Fase B: eliminar repetidamente el elemento de la raíz de H.

Como la raíz de H siempre contiene el mayor de elemento de H, la fase B elimina los elementos de A en orden descendente.

Complejidad de la ordenación por montón

Fase A. suponga que H es un montón. Observe que el numero de comparación para encontrar el sitio adecuado para un  nuevo elemento ITEM de H no puede exceder la por fundida de H. como H es un árbol completo, su profundidad está limitada por log₂  m, donde m es el número de elementos de H. De acuerdo con esto, el número total de comparaciones g(n) para insertar los n elementos de A en H está limitado por la siguiente:

                        g(n)≤n log₂ n

Consecuentemente el tiempo de ejecución de la fase A de la ordenación por montón es proporcional a n long₂ n.

Fase B: suponga que H es 8un árbol completo con m elementos y que los subárboles  izquierdo y derecho de H son montones y que L es la raíz de H. observe que al reamontonar se efectúan cuatro comparaciones para mover el nodo L un paso abajo en el árbol H. como la profundidad H no excede a  long₂ m, al reamontonar se efectúan como mucho 4 log₂  m comparaciones para encontrar el lugar, adecuado de L en el árbol H. esto significa que el número total,  h(n)  de comparaciones para eliminar los n elementos de A en H, los que requieren el reamontonar n veces, está eliminado por:

Así el tiempo de ejecución de la fase B de la ordenación por montón también es proporcional  a n long₂ n.

El tiempo de ejecución para ordenar el array A de n elementos por montón es proporcional  a n long₂ n, o sea, ʄ(n)=0 (n long₂ n), ya que cada fase requiere un tiempo proporcional a n long₂ n. observe que esto da el peor caso en complejidad para el algoritmo. Esto contrasta con los dos siguientes algoritmos de ordenación ya estudiados.

Ordenación  por el método de la burbuja. El tiempo de ejecución de esta ordenación es 0(n²).

Ordenación rápida. El tiempo medio de ejecución de la ordenación rápida es 0(n long₂ n), lo  mismo que la ordenación por montón, pero el tiempo ejecución para el peor caso en la ordenación rápida es proporcional a 0(n²), igual que por el método de la burbuja.