Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::make_heap — izrada hrpe iz raspona

std::make_heap preslaguje raspon u hrpu u linearnom vremenu. Prema zadanim postavkama najveći je element na početku; prilagođeni komparator omogućuje izradu minimalne hrpe. Nije zajamčeno da će dobiveni raspon biti sortiran.

Verzija: 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 zaglavlja <algorithm> pretvara [first, last) u hrpu, preslaguje njezine elemente i vraća void. Raspon ne mora već biti hrpa. Zadana usporedba stvara maksimalnu hrpu: za neprazan raspon *first je najveći element. Time se ne sortira cijeli raspon; točan raspored ostalih elemenata nije specificiran.

Preopterećenje koje prima comp stvara hrpu prema tom komparatoru. Za svako dijete comp(parent, child) mora biti netočno. std::greater<int>{} iz <functional> stvara minimalnu hrpu. Komparator mora definirati strogi slabi poredak; nemojte upotrebljavati <= umjesto <.

Potrebni su iteratori s nasumičnim pristupom, a elementi moraju podržavati zamjenu, konstrukciju premještanjem i dodjelu premještanjem. Za N = last - first algoritam izvodi najviše 3 * N usporedbi, pa je složenost po broju usporedbi linearna. Prazan raspon je valjan, ali tada ne smijete čitati *first ni front().

Primjer provjerava korijen i svojstvo hrpe, umjesto da pretpostavlja određeni raspored svih elemenata. U sljedećim operacijama zadržite isti poredak: std::push_heap, std::pop_heap i std::sort_heap moraju upotrebljavati kompatibilan komparator. Sam std::pop_heap ne uklanja element iz spremnika.

Primjeri

#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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori