CKTIS / C++
std::pop_heap — преместване на корена на купчината в края
std::pop_heap премества корена на непразна купчина в края на диапазона и възстановява купчината в останалия префикс. Не премахва елемент от контейнера. При std::vector извикването на pop_back() премахва извлечения елемент само ако диапазонът на купчината стига до края на вектора.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
std::pop_heap(first, last);
std::pop_heap(first, last, comp);std::pop_heap, декларирана в <algorithm>, работи върху [first, last). Тя премества първоначалния корен на last - 1 и възстановява купчина в [first, last - 1). По подразбиране коренът е най-големият елемент. Вариантът, който приема comp, използва зададения ред; и двата варианта връщат void.
Диапазонът вече трябва да е непразна купчина според същия ред. Итераторите трябва да поддържат произволен достъп, а елементите трябва да позволяват разменяне, конструиране чрез преместване и присвояване чрез преместване. Компараторът трябва да дефинира строго слабо подреждане. Извикването с празен диапазон или с диапазон, който не е купчина, нарушава предусловията.
Алгоритъмът не намалява размера на контейнера. След извикването прочетете извлечения елемент чрез *(last - 1). При std::vector използвайте back(), за да прочетете този елемент, и pop_back(), за да го премахнете, само ако last е равен на итератора end() на вектора. Ако диапазонът свършва по-рано, тези извиквания ще прочетат и премахнат друг елемент. Преди следващо извикване изключете от диапазона преди това извлечения елемент. Броят на сравненията е най-много 2 * log2(N), където N = last - first.
Примерът изгражда купчина с std::make_heap и извежда само гарантирани резултати, а не вътрешното подреждане на купчината. Показаният код е изпълнен без промени и стандартният му изход съвпадна точно с посочения изход. Източникът е развиващ се работен проект, а не фиксираният текст на C++23.
Примери
#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';
}
Резултат
extracted=7 size_before=4 size_after=3 next=4 heap=true
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.