Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::pop_heap — přesunutí kořene haldy na konec

std::pop_heap přesune kořen neprázdné haldy na konec rozsahu a obnoví haldu ve zbývajícím prefixu. Neodstraňuje prvek z kontejneru. U std::vector odstraní pop_back() extrahovaný prvek jen tehdy, pokud rozsah haldy sahá až na konec vektoru.

Verze: C++23; repository compiler flag, production runtime not attested

Syntaxe

#include <algorithm>

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

std::pop_heap, deklarované v <algorithm>, pracuje s rozsahem [first, last). Přesune původní kořen na last - 1 a obnoví haldu v [first, last - 1). Ve výchozím stavu je kořenem největší prvek. Přetížení přijímající comp používá zadané uspořádání; obě přetížení vracejí void.

Rozsah už musí být neprázdnou haldou podle stejného uspořádání. Iterátory musí podporovat náhodný přístup a prvky musí umožňovat výměnu, konstrukci přesunem a přiřazení přesunem. Komparátor musí definovat ostré slabé uspořádání. Volání s prázdným rozsahem nebo s rozsahem, který není haldou, porušuje předběžné podmínky.

Algoritmus nezmenšuje kontejner. Po volání přečtěte extrahovaný prvek pomocí *(last - 1). U std::vector použijte back() k jeho přečtení a pop_back() k jeho odstranění jen tehdy, pokud je last rovno end() vektoru. Pokud rozsah končí dříve, tato volání by přečetla a odstranila jiný prvek. Před dalším voláním vylučte z rozsahu dříve extrahovaný prvek. Počet porovnání je nejvýše 2 * log2(N), kde N = last - first.

Příklad vytvoří haldu pomocí std::make_heap a vypíše pouze zaručené výsledky, nikoli vnitřní uspořádání haldy. Zobrazený kód byl spuštěn beze změn a jeho standardní výstup se přesně shodoval s uvedeným výstupem. Zdrojem je průběžně vyvíjený pracovní návrh, nikoli neměnný text C++23.

Příklady

#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';
}

Výsledek

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

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje