CKTIS / C++
std::push_heap — добавяне на елемент към двоична купчина
std::push_heap възстановява свойството на купчина, след като един елемент е добавен в края на диапазон. Не увеличава размера на контейнера: новият елемент вече трябва да е на last - 1, а предходната част от диапазона трябва да е валидна купчина.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap от заглавния файл <algorithm> включва елемента на позиция last - 1 в купчината върху [first, last). Самата функция не добавя елемент към контейнера и връща void. Обичайната последователност е push_back, последвано от std::push_heap с актуалните итератори.
Преди извикването [first, last - 1) вече трябва да е купчина според същия ред. Диапазонът трябва да съдържа поне новия елемент; не извиквайте алгоритъма за празен диапазон. За създаване на купчина от произволни данни използвайте std::make_heap, а не еднократно извикване на std::push_heap.
Сравнението по подразбиране създава максимална купчина: най-големият елемент е в началото. Вариантът с comp променя реда; std::greater<int>{} създава минимална купчина. Компараторът трябва да задава строго слабо подреждане и да съответства на реда на съществуващата купчина. Купчината не е задължително сортирана.
Необходими са итератори с произволен достъп и елементи, които поддържат разместване, конструиране чрез преместване и присвояване чрез преместване. Броят на сравненията е O(log N), където N = last - first; разходът за предходното push_back е отделен. В примера {9, 5, 7} вече е купчина, затова след добавянето на 12 е достатъчно едно извикване за възстановяване на свойството.
Примери
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> heap{9, 5, 7};
heap.push_back(12);
std::push_heap(heap.begin(), heap.end());
std::cout << "top: " << heap.front() << '\n';
std::cout << "size: " << heap.size() << '\n';
std::cout << "is_heap: " << std::boolalpha
<< std::is_heap(heap.begin(), heap.end()) << '\n';
}
Резултат
top: 12 size: 4 is_heap: true
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.