CKTIS / C++
std::push_heap — dodajanje elementa v kopico
std::push_heap obnovi lastnost kopice, potem ko je na konec območja dodan en element. Velikosti vsebnika ne poveča: novi element mora biti že na mestu last - 1, predhodni del območja pa mora biti veljavna kopica.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap iz glave <algorithm> vključi element na mestu last - 1 v kopico, ki obsega [first, last). Elementa ne doda v vsebnik in vrne void. Običajen postopek je klic push_back, ki mu sledi std::push_heap s trenutnimi iteratorji.
Pred klicem mora biti [first, last - 1) že kopica po istem vrstnem redu. Območje mora vsebovati vsaj novi element; algoritma ne kličite za prazno območje. Za izdelavo kopice iz poljubnih podatkov uporabite std::make_heap, ne enega samega klica std::push_heap.
Privzeta primerjava ustvari maksimalno kopico: največji element je na začetku. Preobremenitev s parametrom comp spremeni vrstni red; std::greater<int>{} ustvari minimalno kopico. Primerjalnik mora določati strogo šibko urejenost in biti skladen z vrstnim redom obstoječe kopice. Kopica ni nujno urejena.
Potrebni so iteratorji z naključnim dostopom in elementi, ki podpirajo zamenjavo, konstrukcijo s premikom ter prirejanje s premikom. Število primerjav je O(log N), pri čemer je N = last - first; strošek predhodnega push_back je ločen. V primeru je {9, 5, 7} že kopica, zato po dodajanju 12 za obnovitev lastnosti kopice zadostuje en klic.
Primeri
#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';
}
Rezultat
top: 12 size: 4 is_heap: true
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.