Como usar algoritmos de heap da STL em C++

Use os algoritmos de heap da STL do C++ para transformar um intervalo de std::vector em um max-heap, ordenar esse intervalo ou mover seu maior valor para o final. std::pop_heap move o valor; se quiser removê-lo do vetor, apague-o separadamente.

Use std::make_heap para transformar um intervalo em um heap

Um heap é um intervalo organizado de modo a obedecer a uma regra entre pais e filhos. Com a comparação padrão, std::make_heap cria um max-heap: cada pai é maior ou igual aos filhos, por isso o maior valor fica no início. Em um heap binário armazenado em um vetor, os filhos do elemento no índice i ficam nos índices 2 * i + 1 e 2 * i + 2, quando essas posições estão dentro do intervalo. Um min-heap usa outra comparação, como std::greater<int>.

std::make_heap reorganiza os elementos para satisfazer a propriedade de heap; não ordena todo o intervalo. Várias disposições podem satisfazer essa mesma propriedade. Por isso, o código deve depender do valor no início e das comparações entre pais e filhos, e não de uma sequência específica de valores após a chamada.

O exemplo independente a seguir cria um heap e verifica a relação entre pais e filhos. Ele foi executado com sucesso, e a saída observada é mostrada abaixo. Os rótulos do bloco de saída permanecem em inglês.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    bool is_max_heap = true;
    for (std::size_t child = 1; child < values.size(); ++child) {
        const std::size_t parent = (child - 1) / 2;
        if (values[parent] < values[child]) {
            is_max_heap = false;
            break;
        }
    }

    std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
    std::cout << "top: " << values.front() << '\n';
}

max-heap: true
top: 91

O elemento no início é o valor do topo do heap. A ordem dos demais elementos do vetor é limitada apenas pela propriedade de heap; portanto, ela não deve ser interpretada como uma lista em ordem crescente ou decrescente.

Use std::sort_heap para ordenar um intervalo de heap

Chame std::sort_heap em um intervalo que já satisfaça a propriedade de heap. Com a comparação padrão, a função reorganiza o intervalo em ordem crescente. Depois da ordenação, o intervalo deixa de satisfazer a propriedade de heap. Antes de usar uma operação de heap em todo o intervalo novamente, chame std::make_heap.

Por exemplo, depois de std::make_heap(values.begin(), values.end()), chame std::sort_heap(values.begin(), values.end()) para ordenar o mesmo intervalo. A comparação padrão produz uma ordem crescente.

A sobrecarga que recebe um comparador aceita uma função ou um objeto de função que define a ordenação. Use a mesma comparação ao construir e ordenar um heap; por exemplo, um heap criado com std::greater<int> deve ser ordenado com esse comparador. A sobrecarga padrão é adequada quando o objetivo é obter uma saída em ordem crescente.

Use std::pop_heap para mover o próximo elemento do heap

std::pop_heap move o valor do topo para a última posição do intervalo e restaura a propriedade de heap no trecho anterior. A função não altera o tamanho do vetor. Para remover esse valor do contêiner, chame pop_back() depois de std::pop_heap.

Para adicionar um elemento, acrescente-o ao vetor e chame std::push_heap. O intervalo anterior ao elemento acrescentado já deve ser um heap; então, std::push_heap restaura a propriedade de heap em todo o intervalo ampliado. Use o mesmo comparador que define o heap em ambas as operações.

Este exemplo independente verifica o valor do topo movido, apaga-o separadamente e, em seguida, adiciona um valor mantendo a propriedade de heap. Ele foi executado com sucesso, e a saída observada é mostrada abaixo. Os rótulos do bloco de saída permanecem em inglês.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "moved top: " << values.back() << '\n';
    values.pop_back();

    values.push_back(95);
    std::push_heap(values.begin(), values.end());
    std::cout << "new top: " << values.front() << '\n';
}

moved top: 91
new top: 95

Depois de std::pop_heap, o prefixo que termina antes do último elemento é o heap que pode ser reutilizado. Quando pop_back() remove o valor final, o próprio vetor volta a conter exatamente esse intervalo de heap. Acrescentar um elemento sem preservar antes essa condição não atende ao pré-requisito de std::push_heap.