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)
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/