CKTIS / C++
std::sort_heap — een bestaande heap sorteren
std::sort_heap zet een heap om in een gesorteerd bereik. De functie vereist random-access-iterators en een bereik dat volgens de gebruikte vergelijking een geldige heap is. Willekeurige invoer kan er niet rechtstreeks mee worden gesorteerd.
Versie: C++23; repository compiler flag, production runtime not attested
Syntax
#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, gedeclareerd in <algorithm>, sorteert de elementen van [first, last) ter plekke en retourneert void. Het bereik moet volgens de vergelijking die std::sort_heap gebruikt al een geldige heap zijn. Roep bij willekeurige invoer eerst std::make_heap aan of gebruik direct std::sort.
De overload zonder comp levert voor getallen een niet-afnemende volgorde op. Een aangepaste comp moet een strikte zwakke ordening definiëren. Die ordening hoeft niet overeen te komen met de ordening waarmee de heap is opgebouwd, zolang het bereik volgens comp een geldige heap is. Als je bijvoorbeeld zowel in std::make_heap als in std::sort_heap std::greater<int>{} gebruikt, ontstaat een niet-toenemend resultaat. Een bereik doorgeven dat geen geschikte heap is, schendt een preconditie.
Random-access-iterators zijn vereist. De elementen moeten voldoen aan de eisen voor verwisselbaarheid, move-constructie en move-toewijzing. Voor N = last - first voert het algoritme hoogstens 2 N log N vergelijkingen uit. Stabiliteit — het behouden van de volgorde van elementen die volgens de vergelijking gelijkwaardig zijn — wordt niet gegarandeerd. Het resultaat is gesorteerd; neem niet aan dat het volgens dezelfde ordening nog een heap is.
Het voorbeeld bouwt eerst een heap op uit vijf getallen en sorteert die vervolgens tot 1 2 3 4 5. Dit artikel beschrijft de klassieke overloads van std::sort_heap, niet de afzonderlijke interface std::ranges::sort_heap. De bron is het huidige concept van de standaard; het voorbeeld is bedoeld voor lokale controle met -std=c++23.
Voorbeelden
#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';
}
Resultaat
1 2 3 4 5
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.