Heap e fila de prioridade: o caso 'top K'

Resposta esperada

Um heap binário é uma árvore quase completa onde todo pai é ≥ (max-heap) ou ≤ (min-heap) que os filhos — dá acesso O(1) ao extremo e inserção/remoção do extremo em O(log n). É a implementação típica de uma fila de prioridade. Pra 'top K de N': mantenha um MIN-heap de tamanho K. Pra cada item do stream, se o heap tem menos de K, insere; senão, se o item é maior que o menor do heap (o topo), remove o topo e insere o item. No fim, o heap tem os K maiores. Custo O(N log K) tempo e O(K) espaço — muito melhor que ordenar tudo (O(N log N)) quando K << N, e funciona em stream sem guardar os N itens. (Min-heap pra 'K maiores' é o detalhe que confunde: o topo é o menor dos candidatos, o primeiro a ser descartado.)