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

CKTIS / C++

std::make_heap — vytvorenie haldy z rozsahu

std::make_heap preusporiada rozsah na haldu v lineárnom čase. Predvolene je najväčší prvok na začiatku; vlastný komparátor umožňuje vytvoriť minimovú haldu. Nie je zaručené, že výsledný rozsah bude zoradený.

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

Syntax

#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> prevedie [first, last) na haldu, preusporiada jej prvky a vracia void. Rozsah nemusí byť vopred haldou. Predvolené porovnávanie vytvorí maximovú haldu: pre neprázdny rozsah je *first najväčší prvok. Celý rozsah sa tým nezoradí; presné usporiadanie ostatných prvkov nie je určené.

Preťaženie s parametrom comp vytvorí haldu podľa tohto komparátora. Pre každého potomka musí byť comp(parent, child) nepravdivé. std::greater<int>{} z <functional> vytvorí minimovú haldu. Komparátor musí definovať striktné slabé usporiadanie; nepoužívajte <= namiesto <.

Potrebné sú iterátory s náhodným prístupom a prvky musia podporovať výmenu, konštrukciu presunom a priradenie presunom. Pre N = last - first vykoná algoritmus najviac 3 * N porovnaní, takže zložitosť podľa počtu porovnaní je lineárna. Prázdny rozsah je platný, ale v takom prípade nesmiete čítať *first ani front().

Príklad kontroluje koreň a vlastnosť haldy namiesto toho, aby predpokladal konkrétne usporiadanie všetkých prvkov. V nadväzujúcich operáciách zachovajte rovnaké usporiadanie: std::push_heap, std::pop_heap a std::sort_heap musia používať kompatibilný komparátor. Samotné std::pop_heap prvok z kontajnera neodstráni.

Prí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ýsledok

max: 7
heap: true
min: 1

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

Zdroje