Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::make_heap — budowanie kopca z zakresu

std::make_heap przestawia elementy zakresu w kopiec w czasie liniowym. Domyślnie największy element trafia na początek; własny komparator pozwala zbudować kopiec minimum. Nie ma gwarancji, że wynik będzie posortowany.

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

Składnia

#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 nagłówka <algorithm> przekształca zakres [first, last) w kopiec, modyfikując kolejność jego elementów i zwracając void. Zakres nie musi wcześniej być kopcem. Domyślne porównanie tworzy kopiec maksimum: dla niepustego zakresu *first jest największym elementem. Nie oznacza to posortowania całego zakresu; dokładny układ pozostałych elementów nie jest określony.

Przeciążenie z comp buduje kopiec zgodny z tym komparatorem. Dla każdego dziecka porównanie comp(parent, child) musi być fałszywe. std::greater<int>{} z <functional> daje kopiec minimum. Komparator musi definiować ścisły słaby porządek; nie używaj <= zamiast <.

Potrzebne są iteratory dostępu swobodnego oraz elementy obsługujące zamianę, konstruowanie przez przeniesienie i przypisanie przez przeniesienie. Dla N = last - first algorytm wykonuje najwyżej 3 * N porównań, czyli ma liniową złożoność liczby porównań. Pusty zakres jest poprawny, ale nie wolno wtedy odczytywać *first ani front().

Przykład sprawdza korzeń i własność kopca, zamiast zakładać konkretny układ wszystkich elementów. W dalszych operacjach zachowuj ten sam porządek: std::push_heap, std::pop_heap i std::sort_heap muszą używać zgodnego komparatora. Samo std::pop_heap nie usuwa elementu z kontenera.

Przykłady

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

Wynik

max: 7
heap: true
min: 1

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła