Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::push_heap — dołączanie elementu do kopca

std::push_heap przywraca własność kopca po dopisaniu jednego elementu na końcu zakresu. Nie zwiększa rozmiaru kontenera: nowy element musi już znajdować się pod last - 1, a wcześniejsza część zakresu musi być poprawnym kopcem.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

#include <algorithm>

std::push_heap(first, last);
std::push_heap(first, last, comp);

std::push_heap z nagłówka <algorithm> włącza element spod last - 1 do kopca obejmującego [first, last). Sam nie dopisuje elementu do kontenera i zwraca void. Typowy schemat to push_back, a następnie std::push_heap z aktualnymi iteratorami.

Przed wywołaniem [first, last - 1) musi już być kopcem według tego samego porządku. Zakres musi zawierać co najmniej nowy element; nie wywołuj algorytmu dla pustego zakresu. Do zbudowania kopca z dowolnych danych służy std::make_heap, a nie pojedyncze wywołanie std::push_heap.

Domyślne porównanie tworzy kopiec maksimum: największy element jest na początku. Przeciążenie z comp pozwala zmienić porządek; std::greater<int>{} tworzy kopiec minimum. Komparator musi określać ścisły słaby porządek i być zgodny z porządkiem istniejącego kopca. Kopiec nie musi być posortowany.

Wymagane są iteratory dostępu swobodnego oraz elementy obsługujące zamianę, konstrukcję przez przeniesienie i przypisanie przez przeniesienie. Liczba porównań wynosi O(log N), gdzie N = last - first; koszt wcześniejszego push_back jest osobny. W przykładzie {9, 5, 7} jest już kopcem, więc po dopisaniu 12 wystarczy naprawić kopiec jednym wywołaniem.

Przykłady

#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';
}

Wynik

top: 12
size: 4
is_heap: true

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła