En un montón mínimo con n elementos con el elemento más pequeño en la raíz, el séptimo elemento más pequeño se puede encontrar en el tiempo
a) 
(n log n)
b) (n)
c) (log n)
d) (1)
La pregunta no estaba clara en el examen GATE original. Para mayor claridad, suponga que no hay duplicados en Min-Heap y que se permite acceder a los elementos del montón por debajo de la raíz.
(A) a
(B) b
(C) c
(D) d
Respuesta: (D)
Explicación: El séptimo elemento más pequeño debe estar en los primeros 7 niveles. El número total de Nodes en cualquier montón binario en los primeros 7 niveles es como máximo 1 + 2 + 4 + 8 + 16 + 32 + 64, que es una constante. Por lo tanto, siempre podemos encontrar el séptimo elemento más pequeño en el 
tiempo.
Si se permite que Min-Heap tenga duplicados, entonces la complejidad del tiempo se convierte en Θ (Log n).
Además, si Min-Heap no permite acceder directamente a los elementos debajo de la raíz y solo admite la operación extract-min(), entonces también la complejidad del tiempo se convierte en Θ(Log n).
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA