Métodos de Ordenamiento: Heapsort

Métodos de Ordenamiento

Los métodos de ordenamiento son ampliamente usados en el desarrollo de software, debido a que posibilitan tomar un grupo de datos (ya sean numéricos o alfabéticos) y ordenarlos de manera secuencial dentro de un tipo de datos de agrupación o arreglo, entro otros.

Heapsort

Es un método de ordenamiento basado con comparación, usa el Montículo o Heap como estructura de datos. Este método es más lento que otros métodos, pero es más eficaz en escenarios más rigurosos.

Se define como un método No Recursivo, No Estable y con Complejidad Computacional.

Formula:

o (n log n)

Montículo

Es una estructura de datos del tipo árbol binario. Este árbol binario tiene que ser completo, en otras palabras, cada nivel debe de estar lleno con excepción del ultimo nivel, en el último nivel, los hijos debe recargarse hacia un mismo lado, generalmente hacia el lado izquierdo, así como se muestra en la imagen de la derecha.

Ventajas y Desventajas

Es usar este método de Ordenamiento trae consigo diversas ventajas y desventajas con respecto a los otros métodos, dichas características están en la tabla a continuación:

Ventajas	Desventajas
•  Funciona efectivamente con datos desordenados. •  Su desempeño es en promedio tan bueno como el Quicksort. •  No utiliza memoria adicional.	•  No es estable. •  Método complejo.

Aplicaciones

Una de las más grandes aplicaciones de Heapsort es construir colas de prioridad con la idea que busque los procesos que llevan la mayor carga de prioridad dado una gran cantidad de procesos por hacer.

En esencia las aplicaciones de Heapsort son las que traten de sobre ordenar una lista de elementos.

Funcionamiento

Este algoritmo consiste en almacenar todos los elementos en un montículo y luego extraer el nodo que queda como raíz en iteraciones sucesivas obteniendo el conjunto ordenado. Para esto el método realiza los siguientes pasos:

1.    Se construye el Heap/montículo a partir del arreglo original.

2.    La raíz se coloca en el arreglo.

3.    El último elemento del montículo se vuelve la raíz.

4.    La nueva raíz se intercambia con el elemento de mayor valor de cada nivel.

5.    Tras el paso anterior la raíz vuelve a ser el mayor del montículo.

6.    Se repite el paso 2 hasta que quede el arreglo ordenado.

Código

Claro para poder aplicar este método es algún software, uno requiere de un código, un cogido que es un tanto largo, enseguida se le mostrara un ejemplo de código en C++ :

void shiftRight(int* arr, int low, int high)

{

    int root = low;

    while ((root*2)+1 <= high)

    {

        int leftChild = (root * 2) + 1;

        int rightChild = leftChild + 1;

        int swapIdx = root;

        /*Check if root is less than left child*/

        if (arr[swapIdx] < arr[leftChild])

        {

            swapIdx = leftChild;

        }

        /*If right child exists check if it is less than current root*/

        if ((rightChild <= high) && (arr[swapIdx] < arr[rightChild]))

        {

            swapIdx = rightChild;

        }

        /*Make the biggest element of root, left and right child the root*/

        if (swapIdx != root)

        {

            int tmp = arr[root];

            arr[root] = arr[swapIdx];

            arr[swapIdx] = tmp;

            /*Keep shifting right and ensure that swapIdx satisfies

            heap property aka left and right child of it is smaller than

            itself*/

            root = swapIdx;

        }

        else

        {

            break;

        }

    }

    return;

}

void heapify(int* arr, int low, int high)

{

    /*Start with middle element. Middle element is chosen in

    such a way that the last element of array is either its

    left child or right child*/

    int midIdx = (high - low -1)/2;

    while (midIdx >= 0)

    {

        shiftRight(arr, midIdx, high);

        --midIdx;

    }

    return;

}

void heapSort(int* arr, int size)

{

    assert(arr);

    assert(size > 0);

    /*This will put max element in the index 0*/

    heapify(arr, 0, size-1);

    int high = size - 1;

    while (high > 0)

    {

        /*Swap max element with high index in the array*/

        int tmp = arr[high];

        arr[high] = arr[0];

        arr[0] = tmp;

        --high;

        /*Ensure heap property on remaining elements*/

        shiftRight(arr, 0, high);

    }

    return;

}

Conclusión

Este método es conveniente cuando se trata de  ordenar arreglos estáticos grandes a diferencia de otros métodos con el Quicksort y el Mergesort. Heapsort compite primariamente con Quicksort, otro método de ordenamiento muy eficiente para propósitos en general.

Referencias

• Paz, E. (2013). Ordenamiento por montículo. Obtenido de http://www.slideshare.net/edopaz/ordenamiento-por-monticulo-heapsort
• Solar, M. (2008). Heapsort. Obtenido de Estructuras de Datos: http://estructuras-de-datos.wikispaces.com/Heapsort
• Solórzano, J. (2012). HeapSort. Obtenido de http://www.slideshare.net/jhosep94/heap-sort-15397805
• Ticona, A., Alvares, D., & Anccasi, O. (2014). ORDENAMIENTO POR MONTICULO (HEAPSORT). Obtenido de https://prezi.com/8otncuqcgpfh/ordenamiento-por-monticulo-heapsort/