CKTIS / C++
std::sort_heap — ordenar um heap existente
std::sort_heap transforma um heap num intervalo ordenado. Exige iteradores de acesso aleatório e um intervalo que seja um heap válido segundo a comparação utilizada pela função; não ordena diretamente dados arbitrários.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#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, declarado em <algorithm>, ordena no próprio intervalo os elementos de [first, last) e devolve void. O intervalo já tem de ser um heap válido segundo a comparação utilizada por std::sort_heap. Para dados arbitrários, chama primeiro std::make_heap ou usa diretamente std::sort.
A sobrecarga sem comp produz uma ordem não decrescente para números. Um comp personalizado tem de definir uma ordenação fraca estrita. Essa ordenação não tem de coincidir com a que foi usada para construir o heap, desde que o intervalo seja um heap válido segundo comp. Por exemplo, usar std::greater<int>{} tanto em std::make_heap como em std::sort_heap produz um resultado não crescente. Passar um intervalo que não seja um heap adequado viola uma pré-condição.
São necessários iteradores de acesso aleatório, e os elementos têm de satisfazer os requisitos de permutabilidade, construção por movimento e atribuição por movimento. Para N = last - first, o algoritmo efetua, no máximo, 2 N log N comparações. A estabilidade — a preservação da ordem dos elementos equivalentes segundo a comparação — não é garantida. O resultado fica ordenado; não assumas que continua a ser um heap segundo a mesma ordenação.
O exemplo constrói primeiro um heap com cinco números e, em seguida, ordena-o para obter 1 2 3 4 5. Esta entrada descreve as sobrecargas clássicas de std::sort_heap, não a interface distinta std::ranges::sort_heap. A fonte é o projeto atual da norma; o exemplo destina-se a verificação local com -std=c++23.
Exemplos
#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';
}
Resultado
1 2 3 4 5
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.