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

CKTIS / C++

std::make_heap — vytvoření haldy z rozsahu

std::make_heap přeuspořádá rozsah na haldu v lineárním čase. Ve výchozím nastavení je největší prvek na začátku; vlastní komparátor umožňuje vytvořit minimovou haldu. Není zaručeno, že výsledný rozsah bude seřazený.

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

Syntaxe

#include <algorithm>

namespace std {

template<class RandomAccessIterator>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

} // namespace std

std::make_heap z hlavičky <algorithm> převede [first, last) na haldu, přeuspořádá její prvky a vrací void. Rozsah nemusí být předem haldou. Výchozí porovnávání vytvoří maximovou haldu: pro neprázdný rozsah je *first největší prvek. Celý rozsah se tím neseřadí; přesné uspořádání ostatních prvků není určeno.

Přetížení s parametrem comp vytvoří haldu podle tohoto komparátoru. Pro každého potomka musí být comp(parent, child) nepravdivé. std::greater<int>{} z <functional> vytvoří minimovou haldu. Komparátor musí definovat striktní slabé uspořádání; nepoužívejte <= místo <.

Jsou potřeba iterátory s náhodným přístupem a prvky musí podporovat výměnu, konstrukci přesunem a přiřazení přesunem. Pro N = last - first provede algoritmus nejvýše 3 * N porovnání, takže složitost podle počtu porovnání je lineární. Prázdný rozsah je platný, ale v takovém případě nesmíte číst *first ani front().

Příklad kontroluje kořen a vlastnost haldy, místo aby předpokládal konkrétní uspořádání všech prvků. V navazujících operacích zachovejte stejné uspořádání: std::push_heap, std::pop_heap a std::sort_heap musí používat kompatibilní komparátor. Samotné std::pop_heap prvek z kontejneru neodstraní.

Příklady

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 7, 3, 2};

    std::make_heap(values.begin(), values.end());
    std::cout << "max: " << values.front() << '\n';
    std::cout << std::boolalpha
              << "heap: " << std::is_heap(values.begin(), values.end()) << '\n';

    std::make_heap(values.begin(), values.end(), std::greater<int>{});
    std::cout << "min: " << values.front() << '\n';
}

Výsledek

max: 7
heap: true
min: 1

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