База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::make_heap — създаване на heap от диапазон

std::make_heap пренарежда диапазон в heap за линейно време. По подразбиране най-големият елемент е в началото; собствен компаратор позволява създаване на минимален heap. Няма гаранция, че полученият диапазон е сортиран.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

#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 от <algorithm> преобразува [first, last) в heap, като пренарежда елементите му, и връща void. Не е необходимо диапазонът вече да е heap. Сравнението по подразбиране създава максимален heap: при непразен диапазон *first е най-големият елемент. Това не сортира целия диапазон; точното подреждане на останалите елементи не е зададено.

Вариантът с comp създава heap според този компаратор. За всяко дете comp(parent, child) трябва да е false. std::greater<int>{} от <functional> създава минимален heap. Компараторът трябва да задава строго слабо нареждане; не използвайте <= вместо <.

Необходими са итератори с произволен достъп, а елементите трябва да поддържат взаимна размяна, конструиране чрез преместване и присвояване чрез преместване. За N = last - first алгоритъмът извършва най-много 3 * N сравнения, така че сложността по брой сравнения е линейна. Празен диапазон е допустим, но тогава не бива да четете *first или front().

Примерът проверява корена и свойството heap, вместо да предполага конкретно подреждане на всички елементи. При следващите операции запазвайте същия ред: std::push_heap, std::pop_heap и std::sort_heap трябва да използват съвместим компаратор. Сам по себе си std::pop_heap не премахва елемент от контейнера.

Примери

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

Резултат

max: 7
heap: true
min: 1

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници