Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

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.

Viri