PUERTA | GATE-IT-2004 | Pregunta 53

Una array de números enteros de tamaño n se puede convertir en un montón ajustando los montones enraizados en cada Node interno del árbol binario completo comenzando en el Node ⌊(n – 1)/2⌋, y haciendo este ajuste hasta el Node raíz (el Node raíz está en el índice 0) en el orden ⌊(n – 1)/2⌋, ⌊(n – 3)/ 2⌋, ….., 0. El tiempo requerido para construir un montón de esta manera es
(A ) O(log n)
(B) O(n)
(C) O (n log log n)
(D) O(n log n)

Respuesta: (B)
Explicación: La declaración anterior es en realidad un algoritmo para construir un Montón de una array de entrada A.

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

El límite superior de la complejidad del tiempo es O(n) para el algoritmo anterior

Ver- https://www.geeksforgeeks.org/g-fact-85/
Cuestionario de esta pregunta