Métodos de Ordenamiento

Mtodos de Ordenamiento: Heapsort
Los mtodos de ordenamiento son ampliamente usados en el desarrollo de software, debido

a que posibilitan tomar un grupo de datos (ya sean numricos o alfabticos) y ordenarlos de
manera secuencial dentro de un tipo de datos de agrupacin o arreglo, entro otros.
Heapsort
Es un mtodo de ordenamiento basado con comparacin, usa el Montculo o Heap como

estructura de datos. Este mtodo es ms lento que otros mtodos, pero es ms eficaz en
escenarios ms rigurosos.
Se define como un mtodo No Recursivo, No Estable y con Complejidad Computacional.
Formula:
o (n log n)
Montculo
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 excepcin del ultimo nivel, en el ltimo
nivel, el hijo 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 mtodo de Ordenamiento trae consigo diversas ventajas y desventajas con
respecto a los otros mtodos, dichas caractersticas estn en la tabla a continuacin:
Ventajas Desventajas
-Funciona efectivamente con datos No es estable.
desordenados. Mtodo complejo.
-Su desempeo es en promedio tan bueno
como el Quicksort.
-No utiliza memoria adicional.
Aplicaciones
Una de las ms 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 montculo y luego extraer el nodo
que queda como raz en iteraciones sucesivas obteniendo el conjunto ordenado. Para esto el
mtodo realiza los siguientes pasos:
1. Se construye el Heap/montculo a partir del arreglo original.
2. La raz se coloca en el arreglo.
3. El ltimo elemento del montculo se vuelve la raz.
4. La nueva raz se intercambia con el elemento de mayor valor de cada nivel.
5. Tras el paso anterior la raz vuelve a ser el mayor del montculo.
6. Se repite el paso 2 hasta que quede el arreglo ordenado.

Cdigo
Claro para poder aplicar este mtodo es algn software, uno requiere de un cdigo, un cogido
que es un tanto largo, enseguida se le mostrara un ejemplo de cdigo 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;
}
Conclusin
Este mtodo es conveniente cuando se trata de ordenar arreglos estticos grandes a diferencia de
otros mtodos con el Quicksort y el Mergesort. Heapsort compite primariamente con Quicksort,
otro mtodo de ordenamiento muy eficiente para propsitos en general.
Referencias
Paz, E. (2013). Ordenamiento por montculo. 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
Solrzano, 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/

Métodos de Ordenamiento

Cargado por

Copyright:

Formatos disponibles

Métodos de Ordenamiento

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Métodos de Ordenamiento

Cargado por

Copyright:

Formatos disponibles

Mtodos de Ordenamiento: Heapsort

Los mtodos de ordenamiento son ampliamente usados en el desarrollo de software, debido

Es un mtodo de ordenamiento basado con comparacin, usa el Montculo o Heap como

Se define como un mtodo No Recursivo, No Estable y con Complejidad Computacional.

1. Se construye el Heap/montculo a partir del arreglo original.

2. La raz se coloca en el arreglo.

3. El ltimo elemento del montculo se vuelve la raz.

4. La nueva raz se intercambia con el elemento de mayor valor de cada nivel.

5. Tras el paso anterior la raz vuelve a ser el mayor del montculo.

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

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

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

int tmp = arr[root];

/*Keep shifting right and ensure that swapIdx satisfies

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

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

void heapSort(int* arr, int size)

assert(size > 0);

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

int high = size - 1;

while (high > 0)

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

int tmp = arr[high];

/*Ensure heap property on remaining elements*/

Paz, E. (2013). Ordenamiento por montculo. Obtenido de

Solar, M. (2008). Heapsort. Obtenido de Estructuras de Datos: http://estructuras-de-

Solrzano, J. (2012). HeapSort. Obtenido de http://www.slideshare.net/jhosep94/heap-

También podría gustarte

/Check if root is less than left child/

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

/This will put max element in the index 0/

/Swap max element with high index in the array/

/Ensure heap property on remaining elements/