Algoritmo de ordenamiento: Heap Sort

Algoritmo de ordenamiento: Heap Sort

1. HEAPSORT
Algoritmo de Ordenamiento
Integrantes:
Daniel Gomez Jaramillo.
Tania Landívar Ordoñez
JonnathanPeñaranda Sarmiento.
Gabriela Verdugo Velesaca.

2. CONTENIDO
1.Introducción
2.Descripcióndelmétodo
I.Ventajasydesventajas.
II.Funcionamiento
III.Complejidadcomputacional
IV.Aplicacionesyusosenlaactualidad
3.Conclusiones
4.Bibliografía.
5.Agradecimientos.

3. INTRODUCCIÓN
Ordenarunalistaeslaoperacióndearreglarloselementosdeacuerdoalgúncriterio(no
necesariamentematemático).Enelcasodetratarsedenúmeroselcriteriodeordenpodríaser
“<”,esdecir,ordenarloselementosdelalistademenoramayor.Aunquenaturalmenteunser
humanoescapazdeimplementarunametodologíapropiaparaordenarunconjuntode
elementos,estatareasevuelveextremadamentecomplicadacuandoelnúmerodeelementoses
grande,puestoquesenecesitaríamuchotiempoysepodríancometererrores.
Ejemplos de esta situación podrían
ser: ordenar alfabéticamente a los
habitantes de una ciudad, ordenar
una biblioteca, clasificar
alfabéticamente las palabras de un
lenguaje, ordenar una serie de
paginas de internet, ordenar un
conjunto de números enteros, etc.

4. DESCRIPCIÓN DEL MÉTODO HEAP SORT
ORIGEN
FuepublicadooriginalmenteporJ.W.J.Williamsllamándolo"Algorithm232"enlarevista
"CommunicationsoftheACM"en1964.
Estealgoritmoconsisteenordenarenunarbolyluegoextraerdelnodoquequedacomoraíz
ensucesivasiteracionesobteniendoelconjuntoordenado.Basasufuncionamientoenuna
propiedaddemontículos,porlacual,lacimasiempredependiendodecómose
definacontendráelmayoromenorelementodelmontículo.
DESCRIPCIÓN GENERAL

5. VENTAJAS Y DESVENTAJAS
VENTAJAS
•Funcionaefectivamentecondatos
desordenados.
•Sudesempeñoesenpromediotan
buenocomoelQuicksort.
•Noutilizamemoriaadicional.
DESVENTAJAS
•Noesestable,yaquesecomportade
maneraineficazcondatosdelmismo
valor
•Estemétodoesmuchomascomplejo
quelosdemás.

6. FUNCIONAMIENTO DEL MÉTODO HEAPSORT
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 por 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.

7. FUNCIONAMIENTO DEL MÉTODO HEAPSORT
<572732126, >,,,,,

8. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
5
7
6
27
23 12
¿5<7?VERDADERO
árbol
ETAPA 1

9. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
5
7
6
27
23 12
¿5<7?VERDADERO

10. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
5
6
27
23 12
¿5<3?FALSO
7
5

11. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
5
6
27
23 12
¿5<2?FALSO
7
5
FALSO¿5<3?

12. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
5
6
27
23 12
¿7<5?FALSO
7
5
¿5<2?FALSO

13. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
5
6
27
23 12
¿7<27?
7
5
VERDADERO¿7<5?FALSO

14. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
6
27
23 12
¿7<27?
7
5
VERDADERO

15. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623 12
5
27
7
¿7<6?FALSO

16. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623 12
5
27
7
¿7<6?FALSO ¿7<12?VERDADERO

17. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623 12
5
27
7
¿7<12?VERDADERO

18. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
5
27
7
12
¿27<12?FALSO

19. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
5
27
7
12
¿27<12?FALSO
27lista_ordenada

20. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
5 12
27
7
27lista_ordenada
FIN ETAPA 1

21. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
5 12
7
27lista_ordenada
FIN ETAPA 1ETAPA 2

22. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
5 12
7
27lista_ordenada
¿5<12?
VERDADERO

23. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
5 12
7
27lista_ordenada
¿5<12?
VERDADERO

24. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
12
27lista_ordenada
5
7
¿7<12?VERDADERO

25. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
12
27lista_ordenada
5
7
¿7<12?VERDADERO

26. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
27lista_ordenada
5 7
12
¿7<6?FALSO

27. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
27lista_ordenada
5
¿12<7?FALSO
¿7<6?FALSO
7
12

28. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
623
27lista_ordenada
5
¿12<7?FALSO
7
12
12

29. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
23
27lista_ordenada
5 7
12
6
2712

30. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
23
27lista_ordenada
5 7
6
2712

31. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
23
5 7
6
27lista_ordenada 2712
¿5<7?
VERDADERO

32. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
23
5 7
6
27lista_ordenada 2712
¿5<7?
VERDADERO

33. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
23
5
¿6<7?VERDADERO
7
6
27lista_ordenada 2712

34. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
23
5
¿6<7?VERDADERO
7
6
27lista_ordenada 2712

35. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
23
5 6
7
272712lista_ordenada 2727127

36. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
3
5 6
lista_ordenada 2727127
2
7

37. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
3
lista_ordenada 2727127
2
5 6
¿5<6?
VERDADERO

38. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
3
5 6
lista_ordenada 2727127
2
¿5<6?
VERDADERO

39. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
6
lista_ordenada 2727127
2
3
5
¿2<6?VERDADERO

40. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
6
lista_ordenada 2727127
2
¿2<6?VERDADERO
3
5

41. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
2727127
2
6
6lista_ordenada
3
5

42. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
lista_ordenada
5 2
3
6
27271276

43. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
lista_ordenada 27271276
5 2
3
¿5<2?
FALSO

44. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
5 2
3
lista_ordenada 27271276
¿3<5?VERDADERO
¿5<2?
FALSO

45. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
2
lista_ordenada 27271276
3
5
¿3<5?VERDADERO

46. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
lista_ordenada 27271276
3 2
5

47. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
27271276
3 5
2
lista_ordenada5

48. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
27271276
3
2
5lista_ordenada
¿2<3?VERDADERO

49. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
27271276
3
2
5lista_ordenada
¿2<3?VERDADERO

50. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
27271276
2
3
5lista_ordenada

51. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
27271276
3
2
5lista_ordenada3

52. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
27271276
2
5lista_ordenada 3

53. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
27271276
2
53lista_ordenada
2

54. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
272712765lista_ordenada 32
árbol = NULL
2
FIN ETAPA 2

55. heap_sort(árbol, lista_ordenada)
{
while(árbol != NULL)
{
insertar_en_monticulo(árbol);
extraer_cima(árbol,lista_ordenada);
borrar_nodo(árbol,pos)
}
}
272712765lista_ordenada 32
árbol = NULL
FIN DEL ALGORITMO
FIN ETAPA 2

56. 272712765lista_ordenada 32
RESULTADO:

57. COMPLEJIDAD DE HEAPSORT
ElalgoritmodeordenaciónpormontículosoHeapSortrecorreelconjuntodeelementos
desdelaposicióndelamitadhastalaprimeraorganizandoelmontículocorrespondientea
dichoelemento.Unavezterminadoesteproceso,seiniciaelprocesodeordenación
intercambiandoelprimerelementoporelúltimodelarregloyreorganizandoelmontículoa
partirdelaprimeraposición.
Lacomplejidaddelalgoritmodeordenaciónpor
montículosesO(nlogn)teniendoencuentaqueel
procesodeorganizarelmontículoenelpeorcaso
solamentetienequehacerintercambiossobreunasola
líneadeelementosdesdelaraízdelárbolhastaalguna
delashojasparaunmáximodenlog(n)intercambios.

58. APLICACIONES Y USOS EN LA ACTUALIDAD
UnadelasmasgrandesaplicacionesdeHeapSortesconstruircolasdeprioridadconlaideaque
busquelosprocesosquellevanlamayorcargadeprioridaddadounagrancantidaddeprocesos
porhacer.
OtraaplicaciónesladeProgramacióndeIntervalos,endondesetieneunalistadetareasconun
tiempodeinicioyfinydeseamoshacertantastareascomoseanposiblesenunperiododetiempo
limitado.
Enesenciaunaaplicaciónoalgoritmoquetratedeordenarunalistadeelementosdependerán
eficientementeenunalgoritmodeordenamiento,yelmétodoHeapSortpuedeproveernosdetal
función.

59. CONCLUSIONES
Laprincipalventajadeestemétododeordenamientoessueficienciaeneltiempodeejecución,
elcualesO(nlogn).Laeficienciadelamemoria,paralaimplementacióndelalgoritmoesO(1),
tantoenlaformaiterativacomorecursiva.
Concluyendo,decimosqueestemétodoesconveniente
usarlocuandosetratadeordenararreglosolistasgrandes,
yaquecuandoporejemplo,esteseencuentracon
elementosrepetidos,elalgoritmosueletener
inconvenientesadiferenciadeotrosmétodoscomoelQuick
SortyelMergeSort.

60. REFERENCIAS BIBLIOGRÁFICAS
•Dr.GuillermoCámaraChávez.(2015).Ordenación.06/06/2016,dehomepages.Sitioweb:
http://homepages.dcc.ufmg.br/~gcamarac/cursos/algoritmia/ordenacion_4pages_sec.pdf
•ConradoMartínez.(2012).Algorítmica:Heapsyheapsort.06/06/2016,dealgorithmicsSitio
web:http://algorithmics.lsi.upc.edu/docs/pqueues.pdf
•Springer-Verlag(1991).“AlgorithmsandDataStrctures”.Ottawa,Canada.06/06/2016,
Disponibleen:https://books.google.com.ec/books?id=NRrcsIJZAYMC

61. ¡¡ GRACIAS !!
Estructura de Datos y Análisis de Algoritmos.