Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::pop_heap — premik korena kopice na konec

std::pop_heap premakne koren neprazne kopice na konec območja in obnovi kopico v preostali predponi. Elementa ne odstrani iz vsebnika. Pri std::vector klic pop_back() odstrani izvzeti element le, če območje kopice sega do konca vektorja.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

#include <algorithm>

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

std::pop_heap, deklariran v <algorithm>, deluje na [first, last). Prvotni koren premakne na last - 1 in obnovi kopico v [first, last - 1). Privzeto je koren največji element. Preobremenitev, ki prejme comp, uporablja podani vrstni red; obe preobremenitvi vrneta void.

Območje mora biti že neprazna kopica po istem vrstnem redu. Iteratorji morajo podpirati naključni dostop, elementi pa morajo omogočati zamenjavo, konstrukcijo s premikom in prirejanje s premikom. Primerjalnik mora določati strogi šibki vrstni red. Klic s praznim območjem ali z območjem, ki ni kopica, krši predpogoje.

Algoritem ne zmanjša velikosti vsebnika. Po klicu preberite izvzeti element z *(last - 1). Pri std::vector uporabite back() za branje tega elementa in pop_back() za njegovo odstranitev le, če je last enak end() vektorja. Če se območje konča prej, bi s tema klicema prebrali in odstranili drug element. Pred naslednjim klicem izključite prej izvzeti element iz območja. Število primerjav je največ 2 * log2(N), pri čemer je N = last - first.

Primer zgradi kopico z uporabo std::make_heap in izpiše samo zagotovljene rezultate, ne notranje razporeditve kopice. Prikazana koda je bila izvedena brez sprememb, njen standardni izpis pa se je natančno ujemal z navedenim izpisom. Vir je sproti razvijajoči se delovni osnutek, ne zamrznjeno besedilo C++23.

Primeri

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

Rezultat

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

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri