Heap sort

Partamos de la base de que podemos representar un heap, o bien heapificamos un arreglo, o bien el contexto del programa ya nos lo venia pidiendo, o lo que sea. Tenemos nuestra lista de elementos ordenada o con la estructura interna de un heap. Bien, esa es la parte dificil.

Si tenemos un heap, ordenar la lista es bastante sencillo, ya que un heap siempre nos puede devolver el maximo (o el minimo) con una complejidad bastante baja. Eso quiere decir que podemos ir desencolando el maximo y meterlo en el final de otro arreglo (o el mismo heap si procuramos que no se desarme). Vamos "de atras hacia adelante", pidiendo los mas grandes y tirandolos al fondo. Semejante al Selection sort, pero aca la idea radica en implementar un heap, por su facilidad de encontrar al maximo.

En terminos de complejidad, el heap sort se encuentra en $O (n \log (n))$ .