CKTIS / C++
std::pop_heap — przeniesienie korzenia kopca na koniec
std::pop_heap przenosi korzeń niepustego kopca na koniec zakresu i odtwarza kopiec w pozostałym prefiksie. Nie usuwa elementu z kontenera. W std::vector można usunąć wyodrębniony element przez pop_back() tylko wtedy, gdy zakres kopca kończy się na końcu wektora.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#include <algorithm>
std::pop_heap(first, last);
std::pop_heap(first, last, comp);std::pop_heap z <algorithm> działa na zakresie [first, last). Przenosi dotychczasowy korzeń pod last - 1 i odtwarza kopiec w [first, last - 1). Domyślnie korzeniem jest największy element. Przeciążenie z comp używa podanej relacji porządkującej; oba przeciążenia zwracają void.
Zakres musi już być niepustym kopcem według tego samego porządku. Iteratory muszą zapewniać dostęp swobodny, a elementy umożliwiać zamianę, konstrukcję przez przeniesienie i przypisanie przez przeniesienie. Komparator musi definiować ścisły słaby porządek. Wywołanie dla pustego zakresu lub zakresu niebędącego kopcem narusza warunki wstępne.
Algorytm nie zmniejsza kontenera. Po wywołaniu odczytaj wyodrębniony element przez *(last - 1). W przypadku std::vector możesz użyć back() do jego odczytania i pop_back() do jego usunięcia tylko wtedy, gdy last jest równe end() wektora. Jeśli zakres kończy się wcześniej, te metody odczytają i usuną inny element. Przed kolejnym wywołaniem wyklucz poprzednio wyodrębniony element z zakresu. Liczba porównań wynosi najwyżej 2 * log2(N), gdzie N = last - first.
Przykład buduje kopiec przez std::make_heap i wypisuje wyłącznie gwarantowane wyniki, nie wewnętrzny układ kopca. Uruchomiono pokazany kod bez zmian, a jego standardowe wyjście dokładnie odpowiadało podanemu wynikowi. Źródłem jest rozwijany szkic standardu, a nie zamrożony tekst C++23.
Przykłady
#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';
}
Wynik
extracted=7 size_before=4 size_after=3 next=4 heap=true
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.