METODO DEL MONTICULO
ORDENACION POR EL METODO DEL MONTICULO
El método de Heapsort es conocido con el nombre de monticulo en el mundo de habla hispana
. Es el metodo mas eficiente de los métodos de ordenacion que trabaja con arboles.
La idea central de este algoritmo consiste en:
1.- Construir un montículo
2.- Eliminar la raíz del montículo en forma repetida
Definición de montículo: 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 par 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.
INSERCION DE UN ELEMENTO EN UN MONTICULO
La insercion de un elemnto en un monticulo 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 condición entonces se efectúa el intercambio.
Si no se cumple 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 en forma recursiva y de abajo hacia arriba.
ELIMINACION DE UN MONTICULO
El proceso para obtener los elementos ordenados se efectúa eliminando la raíz
del montículo en forma repetida.
Los pasos necesarios para lograr la eliminación de la raíz del montículo,
son los siguientes:
1.- Se reemplaza la raíz con el elemento que ocupa la última posición del montículo.
2.- Se verifica si el valor de la raíz es menor que el valor más grande de sus hijos.
Si se cumple la condición, se efectúa el intercambio, si no se cumple,
entonces el algoritmo se detiene y el elemento queda ubicado en su posición
correcta en el monticulo.
* El paso 2 se realiza de manera recursiva de arriba hacia abajo.
ANALISIS DE EFICIENCIA DEL METODO DEl MONTICULO
Debe tenerse en cuenta tanto la fase de construcción del montículo como
la fase donde se elimina repetidamente la raíz del mismo.
A diferencia de lo que pudiera pensarse ya que en la fase de la construcción
del montículo los elementos mayores se cargan a la izquierda y en la fase de la
eliminación de la raíz los elementos menores se cargan a la derecha,
este es un método muy rápido sobre todo para valores grandes de n.
Ejecutar el método del monticulo
