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.