CKTIS / C++
std::pop_heap — de heapwortel naar het einde verplaatsen
std::pop_heap verplaatst de wortel van een niet-lege heap naar het einde van het bereik en herstelt de heap in het resterende prefix. Het verwijdert geen element uit de container. Bij std::vector verwijdert pop_back() het geëxtraheerde element alleen als het heapbereik tot het einde van de vector loopt.
Versie: 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, gedeclareerd in <algorithm>, werkt op [first, last). Het verplaatst de oorspronkelijke wortel naar last - 1 en herstelt een heap in [first, last - 1). Standaard is de wortel het grootste element. De overload met comp gebruikt de opgegeven ordening; beide overloads geven void terug.
Het bereik moet volgens dezelfde ordening al een niet-lege heap zijn. De iterators moeten willekeurige toegang ondersteunen en de elementen moeten verwisselbaar zijn, met moveconstructie en move-toewijzing. De comparator moet een strikte zwakke ordening definiëren. Een aanroep met een leeg bereik of een bereik dat geen heap is, schendt de precondities.
Het algoritme verkleint de container niet. Lees na de aanroep het geëxtraheerde element uit via *(last - 1). Gebruik bij een std::vector alleen back() om het uit te lezen en pop_back() om het te verwijderen als last gelijk is aan end() van de vector. Eindigt het bereik eerder, dan zouden die aanroepen een ander element uitlezen en verwijderen. Sluit vóór een volgende aanroep het eerder geëxtraheerde element uit van het bereik. Het aantal vergelijkingen is hoogstens 2 * log2(N), waarbij N = last - first.
Het voorbeeld bouwt met std::make_heap een heap en drukt alleen gegarandeerde resultaten af, niet de interne indeling van de heap. De getoonde code is ongewijzigd uitgevoerd en de standaarduitvoer kwam exact overeen met de opgegeven uitvoer. De bron is een zich ontwikkelend werkdocument, geen vastgestelde C++23-tekst.
Voorbeelden
#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';
}
Resultaat
extracted=7 size_before=4 size_after=3 next=4 heap=true
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.