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.