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.