CKTIS / C++
std::push_heap — přidání prvku do haldy
std::push_heap obnoví vlastnost haldy poté, co byl na konec rozsahu přidán jeden prvek. Velikost kontejneru nezvětšuje: nový prvek už musí být na pozici last - 1 a předchozí část rozsahu musí být platnou haldou.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap z hlavičky <algorithm> začlení prvek na pozici last - 1 do haldy pokrývající [first, last). Samotný prvek do kontejneru nepřidává a vrací void. Obvyklý postup je zavolat push_back a poté std::push_heap s aktuálními iterátory.
Před voláním už musí být [first, last - 1) haldou podle stejného uspořádání. Rozsah musí obsahovat alespoň nový prvek; algoritmus nevolejte pro prázdný rozsah. Haldu z libovolných dat vytvořte pomocí std::make_heap, nikoli jediným voláním std::push_heap.
Výchozí porovnání vytvoří maximovou haldu: největší prvek je na začátku. Přetížení s parametrem comp změní uspořádání; std::greater<int>{} vytvoří minimovou haldu. Komparátor musí definovat striktní slabé uspořádání a odpovídat uspořádání existující haldy. Halda nemusí být seřazená.
Jsou vyžadovány iterátory s náhodným přístupem a prvky podporující výměnu, konstrukci přesunem a přiřazení přesunem. Počet porovnání je O(log N), kde N = last - first; náklady předchozího push_back jsou samostatné. V příkladu už {9, 5, 7} tvoří haldu, takže po přidání 12 stačí jedno volání k obnovení vlastnosti haldy.
Pří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ýsledek
top: 12 size: 4 is_heap: true
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.