Pregunta 1 · Programació II UDL 2022
Tema: Árboles binarios y heaps · Del examen Examen Segundo Parcial Enero 2022 (2022)
Enunciado
Pregunta 1 (3 puntos). Operaciones sobre max-heap
Considera el max-heap que se ilustra a continuación:
Efectúa de forma independiente las dos operaciones indicadas a continuación sobre el árbol original:
a.
Remove (extracción de la raíz) sobre el max-heap original.
Describe de forma razonada la situación que se produce en cada instante, detallando los intercambios y las configuraciones intermedias hasta alcanzar la disposición definitiva.
b.
Insert del valor 65 sobre el max-heap original.
Describe de forma razonada la situación que se produce en cada instante, detallando los intercambios y las configuraciones intermedias hasta alcanzar la disposición definitiva.
Solución
Según los criterios oficiales de corrección
a. Remove (extracción de la raíz) sobre el max-heap original.
Solución: Extracción de la raíz 60, reubicación del nodo 13 a la raíz y sucesivos intercambios por hundimiento (sift-down): 13 se intercambia con 37, luego con 17, y finalmente con 15. Raíz final: 37.
b. Insert del valor 65 sobre el max-heap original.
Solución: Inserción de 65 como hijo izquierdo de 25 y sucesivos intercambios por flotamiento (sift-up): 65 se intercambia con 25, luego con 31, y finalmente con 60. Raíz final: 65.
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.