Lectura de código real

Leer un top-k

Texto

función top_k(flujo, k):    h ← min-heap vacío    para cada x en flujo:        si tamaño(h) < k: insertar(h, x)        si no, si x > mínimo(h):            extraer_mínimo(h); insertar(h, x)    devolver los elementos de h

¿Qué contiene h al terminar top_k([5, 1, 9, 3, 7, 8], 3) y cuántas veces se llama a extraer_mínimo?5, 7 y 9; el 8 no se compara porque el heap ya está lleno7, 8 y 9; extraer_mínimo se llama 6 veces, una por valor7, 8 y 9; extraer_mínimo se llama 3 veces1, 3 y 5; los tres menores, porque un min-heap guarda los menores