Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::make_heap — ustvarjanje kopice iz območja

std::make_heap v linearnem času preuredi območje v kopico. Privzeto je največji element na začetku; z lastnim primerjalnikom lahko ustvarite minimalno kopico. Ni zagotovljeno, da bodo elementi v dobljenem območju urejeni.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

#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 iz glave <algorithm> pretvori [first, last) v kopico, preuredi njene elemente in vrne void. Območju ni treba biti že kopica. Privzeta primerjava ustvari maksimalno kopico: pri nepraznem območju je *first največji element. S tem se ne uredi celotno območje; natančna razporeditev preostalih elementov ni določena.

Preobremenitev s parametrom comp ustvari kopico v skladu s tem primerjalnikom. Za vsakega otroka mora biti comp(parent, child) neresničen. std::greater<int>{} iz <functional> ustvari minimalno kopico. Primerjalnik mora določati strogo šibko urejenost; namesto < ne uporabljajte <=.

Potrebni so iteratorji z naključnim dostopom, elementi pa morajo podpirati zamenjavo, premikalno konstrukcijo in premikalno prirejanje. Za N = last - first algoritem izvede največ 3 * N primerjav, zato je zahtevnost glede na število primerjav linearna. Prazno območje je veljavno, vendar v tem primeru ne smete brati *first ali front().

Primer preveri koren in lastnost kopice, namesto da bi predpostavljal določeno razporeditev vseh elementov. Pri nadaljnjih operacijah ohranite enak vrstni red: std::push_heap, std::pop_heap in std::sort_heap morajo uporabljati združljiv primerjalnik. Sam std::pop_heap elementa ne odstrani iz vsebnika.

Primeri

#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';
}

Rezultat

max: 7
heap: true
min: 1

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri