PUERTA | PUERTA-CS-2003 | Pregunta 23

En un montón 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)

Respuesta: (D)
Explicación:

Para encontrar el k-ésimo elemento más pequeño, primero tenemos que extraer 6 elementos del montón y luego la raíz del montón resultante será el k-ésimo más pequeño. Complejidad de tiempo total = 6 Extraer-min operaciones = 6*log2n = O(log2n)
Pero podemos encontrar el kth más pequeño del montón utilizando un enfoque inteligente extrayendo elementos del montón de forma no destructiva. Usaremos espacio adicional para crear un nuevo montón mínimo que contendrá un máximo de k elementos en cualquier momento.

Algoritmo:

Inicialice el elemento raíz del montón nuevo con la raíz del montón antiguo (elemento mínimo)

Para k-1 veces, repita lo siguiente:
    extraiga la raíz del nuevo montón mínimo usando extract-min e inserte los 2 elementos secundarios de la raíz extraída del montón original en el nuevo montón. El montón resultante contendrá k elementos y la raíz de los cuales será nuestro k-ésimo más pequeño en el montón original. Esto aumenta el montón nuevo en uno en cada eliminación (eliminar uno, agregar dos), lo que significa que nunca contendrá más de K elementos, por lo que eliminar uno agregar dos tomará O (3 * log (K)) . Después de k iteraciones, es O(3*k*logk) = O(k*logk).
Para implementar esto, los Nodes en el nuevo montón deben almacenar índices de sus Nodes correspondientes en el montón original, en lugar de los valores de los Nodes en sí.
Para 7 elementos, tomará 7log7 = O(1) tiempo ya que el nuevo montón creará solo 7 elementos.

Consulte la pregunta 1 de https://www.geeksforgeeks.org/data-structures-and-algorithms-set-9/

Esta solución es aportada por Pranjul Ahujka
Cuestionario de esta pregunta