Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::pop_heap — presunutie koreňa haldy na koniec

std::pop_heap presunie koreň neprázdnej haldy na koniec rozsahu a obnoví haldu v zostávajúcom prefixe. Neodstraňuje prvok z kontajnera. Pri std::vector odstráni pop_back() extrahovaný prvok len vtedy, keď rozsah haldy siaha až na koniec vektora.

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

Syntax

#include <algorithm>

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

std::pop_heap, deklarované v <algorithm>, pracuje s rozsahom [first, last). Presunie pôvodný koreň na last - 1 a obnoví haldu v [first, last - 1). Predvolene je koreňom najväčší prvok. Preťaženie, ktoré prijíma comp, používa zadané usporiadanie; obe preťaženia vracajú void.

Rozsah už musí byť neprázdnou haldou podľa rovnakého usporiadania. Iterátory musia podporovať náhodný prístup a prvky musia umožňovať výmenu, konštrukciu presunom a priradenie presunom. Komparátor musí definovať ostré slabé usporiadanie. Volanie s prázdnym rozsahom alebo s rozsahom, ktorý nie je haldou, porušuje predbežné podmienky.

Algoritmus nezmenšuje kontajner. Po volaní prečítajte extrahovaný prvok pomocou *(last - 1). Pri std::vector použite back() na jeho prečítanie a pop_back() na jeho odstránenie len vtedy, keď sa last rovná end() vektora. Ak sa rozsah končí skôr, tieto volania by prečítali a odstránili iný prvok. Pred ďalším volaním vylúčte z rozsahu predtým extrahovaný prvok. Počet porovnaní je najviac 2 * log2(N), kde N = last - first.

Príklad vytvorí haldu pomocou std::make_heap a vypíše iba zaručené výsledky, nie vnútorné usporiadanie haldy. Zobrazený kód bol spustený bez zmien a jeho štandardný výstup sa presne zhodoval s uvedeným výstupom. Zdrojom je priebežne sa vyvíjajúci pracovný návrh, nie nemenný text C++23.

Prí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ýsledok

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

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje