ORDENACION POR METODO HEAPSORT

HEAPSORT

• El ordenamiento por heapsort es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional

• El Heapsort está basado en el uso de un tipo especial de árbol binario (llamado apilamiento) para estructurar el proceso de ordenamiento. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en O(n log n).

Caracteristicas

¨ Las llaves están acomodadas en los nodos de tal manera que, para cada nodo i,
Ki <= Kj donde el nodo j es el padre del nodo i. Es decir, al recorrer el camino desde la raíz hacia abajo, las claves se encuentran en orden descendente.

¨ El árbol se llena de izquierda a derecha, lo que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto, éste(os) estará(n) entonces lo más a la izquierda posible del árbol.

Pasos del Heap

1º. Saca el valor máximo del Heap. (El de la posición 1).

2º. Pone el valor sacado en el arreglo ordenado.

3º. Reconstruir el Heap con un elemento menos.

Ejemplo

Ordenamiento : 73 - 50 - 36 - 21 - 46 - 27 - 9 - 18 - 10 - 30