Contenido
Heapsort
------------------------------------------------------------------------------------------- 2
1. Que es heap
-------------------------------------------------------------------------------- 2
2. Que es un
heapsort----------------------------------------------------------------------2
3. Como funciona un
Heapsort-------------------------------------------------------- 2
4. Ventajas y desventajas del
Heapsort------------------------------------------- 3
5. Como llenar y construir un
Heapsort------------------------------------------ 3
6. Interpretacin con Mtodo
grafico--------------------------------------------- 4
7. Ejercicio de
Aplicacin---------------------------------------------------------------- 7
Conclusiones------------------------------------------------------------------------------------- 8
Bibliografa---------------------------------------------------------------------------------------- 9
Web
Grafa----------------------------------------------------------------------------------------9
Heapsort
1. Que es heap
Se dice que un heap (montculo) es un rbol binario quasi-completo,
donde los padres son mayores que los hijos. Tiene una propiedad que
se denomina.
Orden de montculo, y se habla de maximo-heaps o Minimo-heaps.
Este rbol tiene que ser completo, es decir que todos sus niveles
tienen que estar llenos acepto el ultimo, y en este ltimo nivel todos
los hijos deben estar en un mismo lado. (Por ejemplo todos al lado
izquierdo.)
El elemento mximo de un Max-heap se encuentra en la raz. Un
heap de n elementos tiene altura
h = log2(n +
1).
La complejidad del algoritmo de ordenacin por montculos es :
O(n log)n).
Su complejidad en todos los casos es la misma
2. Que es un heapsort
El Heapsort es un mtodo de ordenamiento por seleccin tipo rbol
que organiza los datos y la compara de tal forma que los nodos del
nivel ms bajo estn ms a la izquierda posible y eso permite que al
recorrer el camino desde la raz hacia las hojas los datos se
encuentren en orden descendente y la informacin sea almacenada.
Heapsort es un mtodo de ordenamiento no recursivo.
Heapsort es un mtodo de ordenamiento no estable.
3. Como funciona un Heapsort
Este algoritmo consiste en almacenar todos los elementos del vector
a ordenar en un heap (montculo) y luego extraer el nodo que queda
como raz en sucesivas iteraciones, obteniendo el conjunto ordenado.
Basa su funcionamiento en una propiedad de los montculos, por la
2
cual, la cima siempre depende de cmo se defina el vector puede
contener el mximo valor o el mnimo valor del montculo.
El vector debe tener estructura de montculo, es decir un rbol en el
que los hijos de cada nodo son siempre menores que el padre .De
esta forma no se tiene que recorrer toda la zona desordenada para
encontrar el elemento mximo, ya que en este caso la ordenacin se
realiza en sentido inverso.
4. Ventajas y desventajas del Heapsort
ventajas
Este mtodo funciona ms
efectivamente don datos
desordenados.
No utiliza memoria adicional.
desventajas
No es estable, ya que se
comporta de manera ineficaz
con datos del mismo valor.
Es un mtodo ms complejo.
5. Como llenar y construir un Heapsort
1.
2.
3.
4.
5.
6.
7.
El vector debe tener estructura de montculo, es decir un rbol
en el que los hijos de cada nodo son siempre menores que el
padre.
El rbol se llena de izquierda a derecha, lo que implica que si
algn nodo no est al mismo nivel que los dems, este estar
entonces lo mas a la izquierda posible del rbol.
Se construye el montculo inicial a partir del arreglo original.
Se intercambia la raz con el ltimo elemento del montculo.
El ltimo elemento queda ordenado.
El ltimo elemento se saca del montculo, pero no del arreglo.
Se restaura el montculo haciendo que el primer elemento baje a
la posicin que le corresponde, si sus hijos son menores.
La raz vuelve a ser el mayor del montculo.
Se repite el paso 2 hasta que quede un solo elemento en el
montculo.
6. Interpretacin con Mtodo grafico
Vamos a crear nmeros aleatorios para k=6(donde k=nde nodos)
valor
nodo
3
1
10
15
2
4
17
5
12
6
intercambiamos el nodo 2 con el nodo 5
10
2
17
15
17
12
intercambiamos el nodo 1con el nodo 2.
nodo 1con el nodo 6.
15
10
12
intercambiamos el
17
15
10
12
12
15
10
17
el nodo 6 queda estable.
valor
nodo
12
15
2
4
10
5
intercambiamos el nodo 1con el nodo 3.
12
3
2
15
10
17
15
10
2
12
3
17
intercambiamos el nodo 1con el nodo 5.
17
6
15
10
2
12
3
17
10
2
12
15
17
valor
nodo
3
1
10
12
2
4
intercambiamos el nodo 1con el nodo 2.
3
10
2
12
15
17
10
3
2
12
15
17
intercambiamos el nodo 1con el nodo 3.
15
5
17
6
10
3
2
12
15
17
12
3
2
10
15
17
intercambiamos el nodo 1con el nodo 3.
12
3
2
10
15
17
3
12
10
15
17
valor
nodo
2
1
10
12
4
intercambiamos el nodo 1con el nodo 2.
15
5
17
6
3
12
10
15
17
2
12
10
15
17
valor
nodo
3
1
10
12
4
15
5
17
6
intercambiamos el nodo 1con el nodo 2.
3
2
12
10
15
17
3
12
10
15
17
El arreglo final queda de esta manera
valor
nodo
2
1
10
12
4
15
5
17
6
7. Ejercicio de Aplicacin
Dado un arreglo de 11 elementos generados aleatoriamente. Ordenarlos
mediante el mtodo de Heapsort.
public class HeapsortTes {
public static final int Max=11;
public static void main(String[] args) {
int numero[]=new int[Max];
numero[0]=0;
for (int i = 1; i < Max; i++) {
numero[i]=(int)([Link]()*100+0);
numero[0]++;
int Indice=i;
while (numero[Indice/2]<numero[Indice]&&(Indice/2)!=0) {
int temp=numero[Indice/2];
numero[Indice/2]=numero[Indice];
numero[Indice]=temp;
Indice=Indice/2;
}
}
[Link]("El arreglo es: ");
for (int i = 0; i < Max; i++) {
[Link](" | "+numero[i]);
}
[Link](" | ");
while (numero[0]>0) {
int temp=numero[1];
numero[1]=numero[numero[0]];
numero[numero[0]]=temp;
for (int i = 1; i < numero[0]; i++) {
int Indice=i;
while (numero[Indice/2]<numero[Indice]&&(Indice/2)!
=0) {
int temp2=numero[Indice/2];
numero[Indice/2]=numero[Indice];
numero[Indice]=temp2;
Indice=Indice/2;
}
}
numero[0]--;
}
}
}
[Link]();
[Link]("La matriz ordenada es: ");
for (int i = 0; i < Max; i++) {
[Link](" | "+numero[i]);
}
[Link](" | ");
Conclusiones
El Heapsort est basado en el uso de un tipo especial de rbol binario
(llamado apilamiento) para estructurar el proceso de ordenamiento.
HeapSort consiste esencialmente en convertir el arreglo en un heap.
Construye un arreglo ordenado de atrs hacia adelante (mayor a
menor).
10
Bibliografa
Introduction to Algorithms
Autor: Thomas H. Cormen
Web Grafa
[Link]
[Link]
11
