Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::push_heap — pridanie prvku do haldy

std::push_heap obnoví vlastnosť haldy po pridaní jedného prvku na koniec rozsahu. Veľkosť kontajnera nezväčšuje: nový prvok už musí byť na pozícii last - 1 a predchádzajúca časť rozsahu musí byť platnou haldou.

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

Syntax

#include <algorithm>

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

std::push_heap z hlavičky <algorithm> začlení prvok na pozícii last - 1 do haldy pokrývajúcej [first, last). Samotný prvok do kontajnera nepridáva a vracia void. Zvyčajný postup je zavolať push_back a potom std::push_heap s aktuálnymi iterátormi.

Pred volaním už musí byť [first, last - 1) haldou podľa rovnakého usporiadania. Rozsah musí obsahovať aspoň nový prvok; algoritmus nevolajte pre prázdny rozsah. Na vytvorenie haldy z ľubovoľných údajov použite std::make_heap, nie jediné volanie std::push_heap.

Predvolené porovnanie vytvorí maximovú haldu: najväčší prvok je na začiatku. Preťaženie s parametrom comp zmení usporiadanie; std::greater<int>{} vytvorí minimovú haldu. Komparátor musí definovať striktné slabé usporiadanie a zodpovedať usporiadaniu existujúcej haldy. Halda nemusí byť zoradená.

Vyžadujú sa iterátory s náhodným prístupom a prvky podporujúce výmenu, konštrukciu presunom a priradenie presunom. Počet porovnaní je O(log N), kde N = last - first; náklady predchádzajúceho push_back sú samostatné. V príklade je {9, 5, 7} už haldou, takže po pridaní 12 stačí jedno volanie na obnovenie vlastnosti haldy.

Príklady

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

Výsledok

top: 12
size: 4
is_heap: true

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje