Filas de prioridade e heaps

Dois invariantes

Max-heap junta forma completa e pai maior ou igual aos filhos. Vetor guarda por níveis sem buracos. Raiz é o máximo; o resto não está ordenado.

Com n>0 elementos, os filhos de i são 2*i+1 e 2*i+2. O pai de i>0 é (i-1)/2 com divisão inteira. A altura é $\lfloor\log_2 n\rfloor$.

Subir e descer

• Novo entra no fim e sobe enquanto exceder o pai.
• Saída guarda a raiz, traz o último para o topo e desce pelo maior filho.
• Só o nó mexido pode violar a ordem. Consulta $O(1)$; alteração $O(\log n)$.

Constrói de baixo para cima, dos últimos pais até à raiz:

1. Entrada
   4911247
   Começa no índice 2.
2. Pais 2 e 1
   4127941
   Trocas locais resolvem cada um.
3. Raiz
   1297441
   Desce dois níveis.

Construção $\Theta(n)$. Inserir um a um pode dar $O(n\log n)$.

Ordenar e pedir à biblioteca

• Heapsort troca raiz com o fim ativo e reduz. Pior $O(n\log n)$, auxiliar $O(1)$, sem estabilidade.
• priority_queue é max por omissão. top exige não vazio; pop não devolve.
• Mínimo de max-heap está numa folha, mas não necessariamente na mais funda. Procurar custa $O(n)$.
• Prioridade com índice conhecido sobe ou desce em $O(\log n)$. Achar a posição pode custar $O(n)$.

Top-k maiores usa min-heap de tamanho k. Cordas [4,3,2,6] pagam 5, depois 9, depois 15: total 29.

Provas e código.