CKTIS / C++
std::pop_heap — premještanje korijena hrpe na kraj
std::pop_heap premješta korijen neprazne hrpe na kraj raspona i obnavlja hrpu u preostalom prefiksu. Ne uklanja element iz spremnika. U std::vector poziv pop_back() uklanja izdvojeni element samo ako raspon hrpe seže do kraja vektora.
Verzija: 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 u <algorithm>, radi nad rasponom [first, last). Premješta izvorni korijen na last - 1 i obnavlja hrpu u [first, last - 1). Prema zadanim postavkama korijen je najveći element. Preopterećenje koje prima comp koristi zadani poredak; oba preopterećenja vraćaju void.
Raspon već mora biti neprazna hrpa prema istom poretku. Iteratori moraju podržavati nasumični pristup, a elementi moraju podržavati zamjenu, konstrukciju premještanjem i pridruživanje premještanjem. Usporednik mora definirati strogi slabi poredak. Poziv s praznim rasponom ili rasponom koji nije hrpa krši preduvjete.
Algoritam ne smanjuje veličinu spremnika. Nakon poziva pročitajte izdvojeni element pomoću *(last - 1). U std::vector upotrijebite back() za čitanje tog elementa i pop_back() za njegovo uklanjanje samo ako je last jednak iteratoru end() vektora. Ako raspon završava ranije, tim biste pozivima pročitali i uklonili drugi element. Prije sljedećeg poziva izuzmite prethodno izdvojeni element iz raspona. Broj usporedbi iznosi najviše 2 * log2(N), pri čemu je N = last - first.
Primjer gradi hrpu pomoću std::make_heap i ispisuje samo zajamčene rezultate, a ne unutarnji raspored hrpe. Prikazani kôd izvršen je bez izmjena, a njegov standardni izlaz točno se podudarao s navedenim izlazom. Izvor je radni nacrt koji se kontinuirano razvija, a ne nepromjenjivi tekst C++23.
Primjeri
#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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.