Autor Tema: Heapsort

0 Usuarios y 1 Visitante están viendo este tema.

25 Noviembre, 2012, 06:53 am
Leído 1642 veces

cayitounico

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 303
  • Karma: +0/-0
  • Sexo: Masculino
  • No soy un genio, pero estudiando !aprendo!
Mostrar que el tiempo de ejecucion de Heapifi para el peor caso sobre un heap de tamaño  \(  n \) es de orden \( log(n) \)
R.E.Q.A.

26 Noviembre, 2012, 03:55 am
Respuesta #1

Phicar

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 513
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
Hola, si hablamos de montículos pues es un árbol binario con ciertas propiedades cierto. Bueno, el Heapify va a tratar de convertir el subárbol que le metas en un montículo máximo.
Ahora, como los árboles son binarios y me imagino sabes cómo es el algoritmo tú te vas por los hijos de el nodo que le metes a la función..así que a lo más recorres todos los niveles del arbol y pues la cantidad de nivels en un árbol binario de tamaño n es \( \lceil log_2(n) \rceil \)
redinfocol.org