Estructuras de datos | Montón | Pregunta 6

¿Cuál es el contenido de la array después de dos operaciones de eliminación en la respuesta correcta a la pregunta anterior?
(A) 14,13,12,10,8
(B) 14,12,13,8,10
(C) 14,13,8,12,10
(D) 14,13,12,8,10

Respuesta: (D)
Explicación: para los árboles Heap, la eliminación de un Node incluye las siguientes dos operaciones.

1) Reemplace la raíz con el último elemento en el último nivel.
2) Comenzando desde la raíz, apile el árbol completo de arriba a abajo.

Borremos los dos Nodes uno por uno:
1) Borrado de 25:
Reemplace 25 con 12

          12
        /    \
      /       \
    14        16
   / \         /
 /     \      /
13     10    8

Dado que la propiedad del montón se viola para la raíz (16 es mayor que 12), haga que 16 sea la raíz del árbol.

           16
        /     \
      /        \
    14         12
   / \         /
  /   \       /
13     10    8

2) Eliminación de 16:
Reemplace 16 con 8

           8
        /    \
       /      \
    14         12
   / \
  /   \
 13     10

Apile de raíz a abajo.

           14
         /    \
       /       \
     8         12
    / \
   /   \
 13     10
            14
         /     \
        /       \
     13         12
    / \
   /   \
  8    10

Cuestionario de esta pregunta