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

CKTIS / C++

std::sort_heap — сортиране на съществуваща двоична купчина

std::sort_heap преобразува купчина в сортиран диапазон. Функцията изисква итератори с произволен достъп и диапазон, който е валидна купчина според сравнението, което тя използва; не е предназначена за директно сортиране на произволни данни.

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

Синтаксис

#include <algorithm>

 template<class RandomAccessIterator>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

std::sort_heap, декларирана в <algorithm>, сортира на място елементите от [first, last) и връща void. Диапазонът вече трябва да е валидна купчина според сравнението, което std::sort_heap използва. При произволни данни първо извикай std::make_heap или използвай директно std::sort.

Претоварването без comp подрежда числата в ненамаляващ ред. Потребителският comp трябва да дефинира строго слабо подреждане. То не е задължително да съвпада с подреждането, използвано при изграждането на купчината, стига диапазонът да е валидна купчина според comp. Например употребата на std::greater<int>{} както в std::make_heap, така и в std::sort_heap дава ненарастващ резултат. Подаването на диапазон, който не е подходяща купчина, нарушава предусловие.

Изискват се итератори с произволен достъп, а елементите трябва да отговарят на изискванията за разменяемост, конструиране чрез преместване и присвояване чрез преместване. За N = last - first алгоритъмът извършва най-много 2 N log N сравнения. Стабилността — запазването на реда на елементите, еквивалентни според сравнението — не е гарантирана. Резултатът е сортиран; не приемай, че според същия ред той все още е купчина.

Примерът първо изгражда купчина от пет числа, след което я сортира до 1 2 3 4 5. Тази статия описва класическите претоварвания на std::sort_heap, а не отделния интерфейс std::ranges::sort_heap. Източникът е текущият проект на стандарта; примерът е предназначен за локална проверка с -std=c++23.

Примери

#include <algorithm>
#include <array>
#include <cstddef>
#include <iostream>

int main() {
    std::array<int, 5> values{4, 1, 5, 2, 3};
    std::make_heap(values.begin(), values.end());
    std::sort_heap(values.begin(), values.end());

    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';
}

Резултат

1 2 3 4 5

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

Източници