База знанияИзпитен център
BGБългарски
Избери език13

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници