Heapsort

El ordenamiento

por montículos

(Heapsort en inglés)

DEFINICIÓN 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 :

Aunque el Heapsort tiene un mejor desempeño general que cualquier otro método presentado de clasificación interna, es bastante complejo de programar. El Heapsort fue desarrollado en 1964 por J. W. J. Williams.

 LA ESTRUCTURA DE ESTE ÁRBOL

TIENE LAS SIGUIENTES CARACTERÍSTICAS:

» 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.

»El árbol se llena de izquierda a derecha

VEAMOS GRÁFICAMENTE UN EJEMPLO DE ESTE TIPO DE ÁRBOL:

PASOS QUE REALIZA EL ORDENADOR

Resumiendo, el ordenamiento por Heapsort realiza los siguientes pasos desde un punto de vista de un Heap (con los elementos) y una lista ordenada (inicialmente vacía):

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 EN PSEUDOCODIGO

function heapsort(array A[0..n]): montículo M integer i := 124578 for i = 0..n: insertar_en_monticulo(M, A[i]) for i = 0..n: A[i] =

extraer_cima_del_monticulo(M) return A

funcionamiento del Heapsort