Método de Monticulo

* ORDENACIÓN POR EL MÉTODO DEL MONTÍCULO

El método de Heapsort es conocido con el nombre de montículo, este método es mas eficente que los métodos de ordenación que trabaja con árboles. La idea central de este algoritmo consiste en:

1.- Construir un montículo.

2.- Eliminar la raiz del montículo en forma repetida.

Para todo nodo del árbol se debe cumplir que su valor, sea mayor o igual que el valor de cualquiera de sus hijos. Para representar un montículo en un arreglo lineal debe tenerse en cuenta para todo nodo K, lo siguiente:

1.- El nodo K se almacena en la posición K correspondiente del arreglo.

2.- El hijo izquierdo del nodo K se almacena en la posición 2*K.

3.- El hijo derecho del nodo K se almacena en la posición 2*K + 1.

* INSERCIÓN DE UN ELEMENTO EN UN MONTÍCULO

La inserción de un elemento en un montículo se lleva a cabo de los siguientes pasos:

1.- Se inserta el elemento en la primera posición disponible.

2.- Se verifica si su valor es mayor que el de su padre, si se cumple esta condicón entonces se efectua el intercambio, si no se cumple entonces el algoritmo se detiene y el elemento queda hubicado en su posición correcta en el monticulo.

Cabe aclarar que el paso 2 se aplca en forma recursiva y de abajo hacia arriba

* ELIMINACIÓN DE UN MONTÍCULO

El proceso para obtener los elementos ordenados se efectua eliminando la raíz del montículo en forma repetida. Pasos:

1.- Se reemplaza la raíz con el elemento que ocupa la ultima posición del montículo.

2.- Se verifica si el valor de la raiz es menor que el valor mas grande de sus hijos. Si se cumple la condición se efectua el intercambio, si no se cumple, entonces el algoritmo se detiene y el elemento queda hubicado en su posición correcta en el montículo.

Funcionamiento de Montículo (Heapsort)