Heapsort

Orígenes

Desarrollado por J. Williams en 1964.

Conceptos generales

Árbol binario. Conjunto finito de nodos el cual puede ser vacío o tener un par de árboles llamados izquierdo y derecho. Cuando un nodo no tiene hijos se le llama hoja o nodo terminal.

Heap o montículo. Árbol binario que cumple ciertas condiciones:

1. · El valor de cada nodo es mayor o igual a los valores almacenados en cada uno de sus hijos.
2. · El árbol esta perfectamente balanceado y las hojas del ultimo nivel están todas en las posiciones en el extremo izquierdo.

Definición

Este método es una variante del método por selección, donde la búsqueda del elemento máximo de un arreglo se realiza mediante técnicas basadas en la construcción de un montículo.

Puede ser un montículo ascendente o descendente.

Algoritmo.

1.Se construye el montículo inicial a partir del arreglo original.
2. Se intercambia la raíz con el ultimo elemento del montículo.
3. El ultimo elemento queda ordenado.
4. El ultimo elemento se saca del montículo, no del arreglo.
5. Se restaura el montículo haciendo que el primer elemento baje a la posición que le corresponde, si sus hijos son menores.
6. La raíz vuelve a ser el mayor del montículo.
7. Se repite el paso 2 hasta que quede un solo elemento en el montículo.

Tiempo de ejecución.

•Este método garantiza que el tiempo de ejecución siempre es de:

O(n log n)

•El Heapsort está basado en el uso de un tipo especial de árbol binario. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en n log n.

Ventajas

Su desempeño es en promedio tan bueno como el Quicksort y se comporta mejor que este último en los peores casos.

Desventajas

Aunque el Heapsort tiene un mejor desempeño general que cualquier otro método presentado de clasificación interna, es bastante complejo de programar.

Codigo en C

Funciones a utilizar en HeapSort

heapSort recibe como parametros el vector de datos, y la cantidad de datos.

criba recibe como parametros el vector de datos, posicion izq o raiz del arbol y el limite derecho del monticulo.

void heapSort(int * vector, int num) {
//Ordena un vector de elemetos
int i,j;
int ultimo = num-1;
int aux; //Variable auxiliar para intercambio
for(i = (ultimo-1)/ 2; i>=0; i--){ // ser ordena el monticulo
criba(vector, i, ultimo);
}
// Ordenacion del vector
for(i = ultimo; i>=1; i--){
aux = vector[0];
vector[0] = vector[i];
vector[i] = aux;
criba(vector, 0, i-1);
}

}

void criba(int * vector, int izq, int der){
//Metodo utilizando para ordenacion descendente
int i, j,salir;
int aux; //Variable auxiliar para intercambio de variables
i = izq;
j = 2*i + 1;
aux = vector[i];
salir = 0;
while(j<=der && (salir==0)){
if(j<der)
if(vector[j] < vector[j+1]) j++;   //mayor de los dos hijos
if(aux >= vector[j]) salir = 1;
else{
vector[i] = vector [j];
i = j;
j = 2 * i + 1;
}
}
vector[i] = aux;
}