Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje