Juan Garcés

Personal Blog

Métodos de Ordenamiento

enero 25th, 2013

Ordenamiento por Heapsort

 

Su desempeño es en promedio tan bueno como el Quicksort y se comporta mejor que este último en los peores casos. 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.

El Heapsort está basado en el uso de un tipo especial de árbol binario (llamado apilamiento) para estructurar el proceso de ordenaiento. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en .

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. Es decir, al recorrer el camino desde la raíz hacia abajo, las claves se encuentran en orden descendente.

»El árbol se llena de izquierda a derecha, lo que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto, éste(os) estará(n) entonces lo más a la izquierda posible del árbol.

Veamos gráficamente un ejemplo de este tipo de árbol:


Al enumerar los nodos por niveles, de izquierda a derecha (como se aprecia en la figura), no es necesario usar punteros para almacenar el árbol.

En efecto, se puede usar un arreglo A[1..n], donde los hijos de A[i] son A[2*i] y A[2*i+1]. Así, la condición del Heap se puede reformular:

A[i] > A[2*i]
A[i] > A[2*i+1]

Luego un vector con las llaves quedaría de la siguiente forma:

73 – 50 – 36 – 21 – 46 – 27 – 9 – 18 – 10 – 30

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.

El proceso de sacar el máximo (la raíz) lleva en sí una serie de pasos más que son:

** Toma el elemento de la raíz y lo intercambia con el elemento más a la derecha de la rama que esté en el nivel más bajo. Recordemos que el árbol (Heap) se llena de izquierda a derecha, con lo cual, el proceso de sacar la raíz se hace en forma inversa (Vaciando el árbol).

** Al intercambiar la raíz con el elemento antes mencionado, se produce un quiebre en las condiciones del Heap, con lo cual se debe reconstruir y volver a dejar en la raíz del árbol el elemento que es mayor que todos los demás.

Un algoritmo sencillo para visualizar cómo funciona este método de ordenamiento puede ser el siguiente:

void HeapSort(Lista Numeros)
{
    Heap=Construir_Heap(Numeros);
    while(Heap_vacio(Heap)==0)
    {
        Auxiliar=Extraer_Max(Heap);
        Insertar(Ordenada, Auxiliar);
        Ultimo=Ultimo_Heap(Heap);
        Numeros=Coloca_Cabeza(Ultimo,Numeros);
        Heap=Reconstruir_Heap(Heap);
    };
};

Otra forma de implementarlo sería la siguiente, realiza el proceso con un vector.

void swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

void HeapSort(Lista vec,int n)
{
    int i,j;
    for (i=0;i<n;i++)
    {
        j=i+1;
        while(j>1)
            if (vec[j-1]>vec[j/2-1]){
                swap(vec[j-1],vec[j/2-1]);
                j/=2;
            }
            else
                break;
    }
    for(i=n-1;i>0;i–)
    {
        swap(vec[0],vec[i]);
        j=1;
        while (j*2<i)
            if (j*2+1>i)
                if (vec[j-1]>vec[j*2-1])
                    break;
                else{
                    swap(vec[j-1],vec[j*2-1]);
                    j*=2;
                }
            else
                if (vec[j*2-1]>vec[j*2])
                    if (vec[j-1]>vec[j*2-1])
                        break;
                    else{
                        swap(vec[j-1],vec[j*2-1]);
                        j*=2;
                    }
                else
                    if (vec[j-1]>vec[j*2])
                        break;
                    else{
                        swap(vec[j-1],vec[j*2]);
                        j*=2+1;
                    }
    }
}

En promedio, el número requerido de comparaciones e intercambios para el Heap Sort es: lo cual es . En el peor de los casos, este número se incrementa a . El peor caso no es mucho peor que el caso promedio. El método de ordenamiento por Heapsort garantiza un tiempo de proceso de . Para un tamaño “n” muy grande, la complejidad del algoritmo está compensada por la eficiencia del método.

 

Juan Garcés

Personal Blog