Estructuras de datos | Montón | Pregunta 1 – Part 2

¿Cuál es la complejidad de tiempo de la operación Build Heap? Build Heap se usa para construir un montón binario máximo (o mínimo) a partir de una array determinada. Build Heap se usa en Heap Sort como un primer paso para ordenar.
(A) O(nLogn)
(B) O(n^2)
(C) O(Logn)
(D) O(n)

Respuesta: (D)
Explicación: El siguiente es 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

Aunque la complejidad del peor de los casos parece O(nLogn), el límite superior de la complejidad del tiempo es O(n). Consulte los siguientes enlaces para ver la prueba de la complejidad del tiempo.

Tiempo Complejidad de construir un montón
Cuestionario de esta pregunta