Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::is_heap — provjera svojstva hrpe

std::is_heap provjerava zadovoljava li raspon svojstvo hrpe, a da pritom ne mijenja njegove elemente. Prema zadanim postavkama prepoznaje maksimalnu hrpu; prilagođeni komparator omogućuje provjeru drugog poretka, primjerice minimalne hrpe.

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

Sintaksa

#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)

std::is_heap, deklarirana u <algorithm>, vraća bool nakon provjere raspona [first, last). Zahtijeva valjan raspon i iteratore s nasumičnim pristupom, kao što su iteratori std::array ili std::vector. Ne izrađuje niti popravlja hrpu i ne preslaguje elemente. Prazan raspon ili raspon s jednim elementom zadovoljava uvjet.

Za svaki indeks djeteta i > 0, indeks roditelja je (i - 1) / 2, uz cjelobrojno dijeljenje. Uvjet hrpe zahtijeva da comp(parent, child) bude false. Zadana usporedba std::less{} za brojeve daje maksimalnu hrpu: roditelj nije manji od djeteta. std::greater<int>{} provjerava minimalnu hrpu. Komparator mora definirati strogi slabi poredak; upotrijebite isti poredak kao pri izradi hrpe.

Hrpa ne mora biti sortirana: ne zahtijeva se relativni poredak među braćom. Provjera ima linearnu složenost u odnosu na broj elemenata. Rezultat je jednak provjeri std::is_heap_until(first, last, comp) == last; ta druga funkcija pomaže pronaći prvo narušavanje. Za izradu hrpe upotrijebite std::make_heap.

Primjer najprije prepoznaje maksimalnu hrpu, zatim je odbacuje kao minimalnu hrpu i naposljetku otkriva narušavanje u odnosu na roditelja vrijednosti 5 nakon dodjele values[3] = 10. Prikazana preopterećenja bez politike izvođenja su constexpr; postoje i preopterećenja s politikom izvođenja. Ovaj se zapis odnosi na C++23. Izvor je nacrt standarda koji se razvija, a zastavica prevoditelja u repozitoriju ne potvrđuje produkcijsko okruženje.

Primjeri

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

int main() {
    std::array<int, 5> values{9, 5, 8, 1, 3};
    std::cout << std::boolalpha;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
    std::cout << std::is_heap(values.begin(), values.end(),
                              std::greater<int>{}) << '\n';
    values[3] = 10;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
}

Rezultat

true
false
false

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

Izvori