Metodo Heapsort

Ordenación por el método heapsort (montículo)
El método de ordenación heapsort se conoce también como montículo. Su nombre se debe a su autor, J. W. Williams, quien lo llamó así. Es el más eficiente de los métodos, de ordenación que trabajan con árboles. La idea central de este algoritmo se basa en las operaciones:
* Construir un montículo.
* Eliminar la raíz del montículo en formarepetida.
En la figura se muestra un montículo. Allí se puede observar que para cada nodo del árbol, su valor es mayor o igual que el valor de cualquiera de sus hijos.

En la figura se muestra un montículo. Allí se puede observar que para cada nodo del árbol, su valor es mayor o igual que el valor de cualquiera de sus hijos.

Es importante señalar que un montículo se define como: Para todo nododel árbol debe cumplir que su valor sea mayor o igual que el valor de cualquiera de sus hijos.
67
36
60
28
21
56
44
15
67
36
60
28
21
56
44
15

Ahora bien, para representar un montículo en un arreglo lineal se debe tener e-cuenta para todo nodo K lo siguiente:

* El nodo K se almacena en la posición K correspondiente del arreglo.
* El hijo izquierdo del nodo K se almacenaen la posición 2 * K.
* El hijo derecho del nodo K se almacena en la posición 2 * K + 1.

A

A

67 | 36 | 60 | 28 | 21 | 56 | 44 | 15 |

Inserción de un elemento en un montículo

La inserción de un elemento en un montículo se lleva a cabo por medio de los siguientes pasos:
* Se inserta el elemento en la primera posición disponible.
* Se verifica si su valor es mayor que elde su padre. Si se cumple esta condición, entonces se efectúa el intercambio. Si no se cumple esta condición, entonces el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo.
Cabe aclarar que el paso 2 se aplica de manera recursiva y desde abajo hacia arriba.

Inserciones en un montículo (NOTA: se utiliza la flecha descontinua para indicar la posicióninicial donde se inserta el o los elementos).

60
15
16
08
60
16
15
08
60
15
16
08
60
16
15
08
A) Insertar clave 08 y 16
B) Insertar clave 08 y 16
C) Insertar clave 44
D) Insertar clave 44
60
16
15
08
44
60
44
15
08
16
60
16
15
08
44
60
44
15
08
16
Ejemplo: Insertando claves en un montículo
Ejemplo: Insertando claves en un montículo
E) Insertarclave 60
F) Insertar clave 60
G) Insertar clave 15
H) Insertar clave 15
15
60
60
15
15
60
60
15
15
15
E

Algoritmo Insertar_monticulo:
{El algoritmo inserta los elementos en un montículo representado como arreglo. A es un arreglo unidimensional de N elementos}
1. Repetir con I desde 2 hasta N
Hacer K<— I y BAND <— VERDADERO
2.1 Mientras ((K > 1) y(BAND = VERDADERO)) Repetir
Hacer BAND <— FALSO
1.1.1 Si (A[K] > A[Parte entera(K entre 2))] entonces
Hacer AUX <— A[Parte entera entera(K entre 2)]
A[Parte entera(K entre 2)] <— A[K],A[K] <— AUX,
K <— parte entera (K entre 2) y BAND <— VERDADERO
1.1.2 {Fin de la condición del paso 1.1.1}
1.2 {Fin del ciclo del paso 1.1}
2. {Fin del paso 1}

Eliminaciónde un montículo
El proceso para obtener los elementos ordenados se efectúa eliminando la raíz del mon-tículo en forma repetida. Ahora bien, los pasos necesarios para lograr la eliminación de la raíz del montículo son:
* Se reemplaza la raíz con el elemento que ocupa la última posición del montículo.
* Se verifica si el valor de la raíz es menor que el valor más grande de sus hijos. Si secumple la condición, entonces se efectúa el intercambio. Si no se cumple la condi-ción, entonces el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo.
Cabe aclarar que el paso 2 se aplica de manera recursiva y desde arriba hacia abajo.
Supongamos que se desea eliminar la raíz del montículo (67) de la figura. Remplazamos la raíz, 67, por el elemento que...