PUERTA | PUERTA-CS-2009 | Pregunta 60 – Part 7

Considere los datos dados en la pregunta anterior. ¿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.

Let us delete the two nodes one by one:
1) Deletion of 25:
Replace 25 with 12

          12
        /    \
      /       \
    14        16
   / \         /
 /     \      /
13     10    8
Since heap property is violated for root (16 is greater than 12),
make 16 as root of the tree.

           16
        /     \
      /        \
    14         12
   / \         /
  /   \       /
13     10    8
2) Deletion of 16:
Replace 16 with 8

           8
        /    \
       /      \
    14         12
   / \
  /   \
 13     10
Heapify from root to bottom.

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

Cuestionario de esta pregunta