Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::pop_heap — mover a raiz do heap para o fim

std::pop_heap move a raiz de um heap não vazio para o fim do intervalo e restabelece o heap no prefixo restante. Não elimina nenhum elemento do contentor. Num std::vector, pop_back() só remove o elemento extraído se o intervalo do heap se estender até ao fim do vetor.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#include <algorithm>

std::pop_heap(first, last);
std::pop_heap(first, last, comp);

std::pop_heap, declarado em <algorithm>, opera sobre [first, last). Move a raiz original para last - 1 e restabelece um heap em [first, last - 1). Por predefinição, a raiz é o maior elemento. A sobrecarga que recebe comp utiliza a ordenação fornecida; ambas as sobrecargas devolvem void.

O intervalo já tem de ser um heap não vazio segundo a mesma ordenação. Os iteradores têm de suportar acesso aleatório e os elementos têm de permitir troca, construção por movimento e atribuição por movimento. O comparador tem de definir uma ordenação fraca estrita. Chamar a função com um intervalo vazio ou com um intervalo que não seja um heap viola as pré-condições.

O algoritmo não reduz o tamanho do contentor. Após a chamada, lê o elemento extraído através de *(last - 1). Num std::vector, usa back() para o ler e pop_back() para o remover apenas se last for igual a end() do vetor. Se o intervalo terminar antes, essas chamadas leem e removem outro elemento. Antes de uma nova chamada, exclui do intervalo o elemento extraído anteriormente. O número de comparações é, no máximo, 2 * log2(N), em que N = last - first.

O exemplo constrói um heap com std::make_heap e apresenta apenas resultados garantidos, não a disposição interna do heap. O código apresentado foi executado sem alterações e a sua saída padrão coincidiu exatamente com a saída indicada. A fonte é um projeto de norma em evolução, não o texto fixo de C++23.

Exemplos

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

int main() {
    std::vector<int> values{4, 1, 7, 3};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "extracted=" << values.back() << '\n';
    std::cout << "size_before=" << values.size() << '\n';

    values.pop_back();
    std::cout << "size_after=" << values.size() << '\n';
    std::cout << "next=" << values.front() << '\n';
    std::cout << "heap=" << std::boolalpha
              << std::is_heap(values.begin(), values.end()) << '\n';
}

Resultado

extracted=7
size_before=4
size_after=3
next=4
heap=true

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova da verificação desta versão exata.

Fontes