Filas de prioridade e heaps

Uma fila de prioridade permite inserir e consultar ou retirar o elemento mais prioritário. Não oferece, por si só, pesquisa eficiente de uma chave arbitrária nem um percurso ordenado. Uma heap binária é uma representação deste TAD.

Assume vetores e índices a partir de zero da página de C++. A novidade são os dois invariantes que permitem guardar a árvore sem apontadores e reparar a ordem com subidas e descidas.

Dois invariantes independentes

Uma max-heap tem a forma de uma árvore binária completa e cada pai tem valor maior ou igual ao dos filhos. A forma permite guardar os nós por níveis num vetor sem buracos; a ordem garante que o máximo está na raiz. Não obriga o filho esquerdo a ser menor que o direito, nem impõe a ordem de uma BST.

Com índices a partir de zero, os filhos de i são 2*i+1 e 2*i+2, quando essas posições existem. O pai de i>0 é (i-1)/2. Numa convenção a partir de um, as fórmulas mudam para 2*i, 2*i+1 e i/2. Não mistures as duas.

O vetor [12,9,7,4,4,1] representa uma max-heap: 12 tem filhos 9 e 7; 9 tem filhos 4 e 4; 7 tem filho 1. A altura é $\lfloor\log_2 n\rfloor$ para n>0. O vetor não está ordenado, mas qualquer descendente é no máximo o seu antepassado.

Inserir e retirar

Para inserires, acrescenta o valor no fim, conservando a forma completa. Só o caminho do novo nó até à raiz pode violar a ordem. Enquanto o valor exceder o pai, troca-os e sobe. Em [9,4,7], inserir 12 produz [9,4,7,12], depois [9,12,7,4] e finalmente [12,9,7,4].

Para retirares o máximo, guarda a raiz, põe o último elemento na raiz e reduz o tamanho. As subárvores já são heaps; só a nova raiz pode violar a prioridade. Troca-a com o maior filho enquanto esse filho for maior. Escolher sempre o esquerdo pode deixar o direito acima do pai.

O invariante da descida é que a única possível violação está no nó atual e que as subárvores abaixo dele são heaps. A troca com o maior filho repõe a ordem no nó antigo; a possível violação desce um nível. Empates não exigem troca.

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
class Heap {
    std::vector<int> a;
    void descer(std::size_t i) {
        while (i < a.size() / 2) {
            std::size_t j = 2 * i + 1;
            if (j + 1 < a.size() && a[j] < a[j + 1]) ++j;
            if (a[j] <= a[i]) break;
            std::swap(a[i], a[j]); i = j;
        }
    }
public:
    explicit Heap(std::vector<int> v) : a(std::move(v)) {
        for (std::size_t i = a.size() / 2; i > 0; --i) descer(i - 1);
    }
    bool retirar(int& x) {
        if (a.empty()) return false;
        x = a.front(); a.front() = a.back(); a.pop_back();
        if (!a.empty()) descer(0);
        return true;
    }
};
int main() {
    Heap h({4, 9, 1, 12, 4, 7}); int x; bool primeiro = true;
    while (h.retirar(x)) { std::cout << (primeiro ? "" : " ") << x; primeiro = false; }
    std::cout << "\nvazio: " << !h.retirar(x) << '\n';
}

retirar devolve falso no vazio, porque uma heap vazia não tem raiz para consultar. Os dois valores 4 conservam-se como elementos distintos. O custo de inserir e retirar é $O(\log(n+1))$; consultar o máximo custa $O(1)$.

Mínimo e alteração de prioridade

Numa max-heap, existe um mínimo numa folha: se um nó mínimo tiver filhos, estes não podem ser maiores que ele nem menores que o mínimo, pelo que algum descendente folha tem o mesmo valor. Isso não obriga todas as ocorrências mínimas a serem folhas, pois todos os valores podem ser iguais.

Uma folha pode estar um nível acima das folhas mais profundas. Em [9,8,1,7,6], o mínimo 1 é folha na profundidade 1; as folhas 7 e 6 estão na profundidade 2. Portanto procurar o mínimo apenas no nível mais profundo falha. Num vetor de max-heap não vazio, basta examinar as posições de folhas, [n/2,n), mas o pior caso continua linear.

Se já conheces o índice do valor a alterar, aumentar a prioridade numa max-heap só pode violar a ligação com o pai, pelo que sobe. Diminuí-la só pode violar as ligações com os filhos, pelo que desce pelo maior filho. Em [15,10,12,4,8,7], mudar o índice 4 de 8 para 20 sobe por 10 e 15, dando [20,15,12,4,10,7]. Partindo de novo do original, mudar a raiz de 15 para 6 desce por 12 e 7, dando [12,10,7,4,8,6].

A reparação custa $O(\log n)$ porque percorre um caminho. Encontrar antes uma chave arbitrária pode custar $O(n)$. Se mantiveres um mapa de chave para índice, atualiza-o a cada troca. A vantagem do vetor para a heap vem da forma completa: calcula pai e filhos sem guardar apontadores por nó e mantém os valores contíguos em memória.

Construção em tempo linear

Inserir os elementos um a um custa $O(n\log n)$ no pior caso. Para construir a partir de um vetor, começa no último pai, índice n/2-1 para n>=2, e desce em cada pai até à raiz. As folhas já são heaps de um nó; quando chega a vez de um pai, os seus filhos já foram tratados.

Ler o vetor já exige $\Omega(n)$, pelo que construir é $\Theta(n)$.

Heapsort

Constrói uma max-heap, troca a raiz com a última posição ativa, reduz a região da heap e volta a descer a raiz. O prefixo [0,k) continua a ser heap e o sufixo [k,n) já está ordenado. Com [12,9,7,4,4,1], trocar 12 com 1 e descer da raiz repõe [9,4,7,4,1] no prefixo e fixa 12 no fim. O sufixo contém os maiores valores nas posições finais, por ordem crescente. Ao terminar, o vetor inteiro está crescente.

Construção linear seguida de n-1 retiradas dá $O(n\log n)$ no pior caso. A implementação iterativa usa $O(1)$ de espaço auxiliar sobre o vetor e não é estável. Na biblioteca, make_heap, push_heap e pop_heap operam sobre uma região; pop_heap move o extremo para o fim, mas não reduz o container. Tens de retirar o último elemento depois, se esse for o objetivo.

Prioridades, empates e top-k

std::priority_queue<int> é uma max-heap. Para min-heap declara std::priority_queue<int,std::vector<int>,std::greater<int>>. Para pares ordenados por preço, usa std::priority_queue<std::pair<int,std::string>> na max-heap e o comparador greater na min-heap. top exige heap não vazia; pop não devolve o valor. Com registos, define primeiro a prioridade e depois o desempate, por exemplo menor instante e, no empate, menor número de sequência. Sem desempate, não assumes FIFO entre prioridades iguais.

Para conservares os k maiores valores de um fluxo, mantém uma min-heap com no máximo k elementos. Se estiver cheia e o novo valor não exceder a raiz, descarta-o; caso contrário substitui a raiz. O invariante é que a heap contém os maiores k elementos processados, com multiplicidades, quando já existem pelo menos k. Tempo $O(n\log(k+1))$, espaço $O(k)$. Para k=0, não consultes a raiz: a resposta é vazia.

Para juntar cordas, a min-heap oferece as duas menores em cada passo. Em [4,3,2,6], junta 2 e 3, reinsere 5 e acrescenta 5 ao custo. Depois junta 4 e 5, pagando 9, e finalmente 6 e 9, pagando 15. O custo total é 5+9+15=29; a soma final 15 é o comprimento da corda, não o custo acumulado. Esta aplicação é trabalhada na ficha 12 de 2025/26.

Uma heap dá o extremo depressa, mas procurar ou alterar uma chave arbitrária pode custar $O(n)$ sem uma estrutura auxiliar que conheça a sua posição. Alterar um valor no vetor exige voltar a subir ou descer conforme a direção da alteração.