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/
Muy completo c:
ResponderBorrarMuy buen trabajo Luis!
ResponderBorrarMuy buena investigacion del algoritmo de ordenamiento, gracias.
ResponderBorrarBuen trabajo, es el que mejor entendí en clase, me gusto este método
ResponderBorrarMuy buen blog, dan ganas de compartirlo :)
ResponderBorrarEs el algoritmo que mas me sorprendio de todos. Supongo que es porque es el más visual y curioso. Me agrada, es el primo de Quicksort por su nivel de eficiencia y complejidad jajaja.
ResponderBorrarExcelente post
ResponderBorrarmuy buena explicacion
ResponderBorrarGracias muy buena explicación y post.
ResponderBorrar1xbet korean ᐈ Top 10 Online Bookmakers in Korea
ResponderBorrar1xbet 샌즈카지노 korean. The 1xbet site offers a large selection of gaming products. Its games are developed หารายได้เสริม by Microgaming with an emphasis on sports betting and 1xbet korean
Lucky Club Casino Site
ResponderBorrarLucky Club Casino is a modern online casino with a live casino experience that can be played without the need for registration or registration. Rating: 5 · Review by 카지노사이트luckclub LuckyClub.live
Casino Review 2021 - New Jersey | Mapyro
ResponderBorrarCasino was launched in 1998 and has since become one of the oldest 대전광역 출장안마 and most popular 문경 출장안마 gambling 구미 출장마사지 sites in 김해 출장샵 New Jersey. The casino has a 광명 출장마사지 large