Heapsort

Para comenzar diremos la definición: un heap (binario) es un arreglo que puede verse como un árbol binario completo:

• Cada nodo del árbol corresponde a un elemento del arreglo
• El árbol está lleno en todos los niveles excepto posiblemente el de más abajo, el cual está lleno desde la izquierda hasta un cierto punto.

Es un método de ordenamiento que se caracteriza porque reúne todos los elementos de un vector o arreglo como quieran llamarlo, de izquierda a derecha para luego extraer el montículo que quedo como la raíz del array (o sea en la cima), y esto lo hace la cantidad de veces necesarias.

Este algoritmo inserta los elementos del vector en un “montículo” y aprovecha que de esta manera tendremos siempre el mayor elemento en la raíz. Para obtener los elementos ordenados de mayor a menor, se debe tomar el valor de la raíz, eliminar la raíz y reordenar el “montículo” hasta agotar sus nodos.

* vídeo que ejemplifica el método de ordenamiento.