WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::sort_heap — einen vorhandenen Heap sortieren

std::sort_heap wandelt einen Heap in einen sortierten Bereich um. Die Funktion erfordert Random-Access-Iteratoren und einen Bereich, der gemäß dem von ihr verwendeten Vergleich ein gültiger Heap ist. Beliebige Eingaben lassen sich damit nicht direkt sortieren.

Version: 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 aus <algorithm> sortiert die Elemente von [first, last) direkt im Bereich und gibt void zurück. Der Bereich muss gemäß dem von std::sort_heap verwendeten Vergleich bereits ein gültiger Heap sein. Bei beliebigen Eingaben rufe zuerst std::make_heap auf oder verwende direkt std::sort.

Die Überladung ohne comp erzeugt bei Zahlen eine nicht absteigende Reihenfolge. Ein benutzerdefiniertes comp muss eine strikte schwache Ordnung festlegen. Diese muss nicht mit der Ordnung übereinstimmen, mit der der Heap erstellt wurde, solange der Bereich gemäß comp ein gültiger Heap ist. Werden beispielsweise sowohl für std::make_heap als auch für std::sort_heap std::greater<int>{} verwendet, ist das Ergebnis nicht zunehmend. Die Übergabe eines Bereichs, der kein geeigneter Heap ist, verletzt eine Vorbedingung.

Erforderlich sind Random-Access-Iteratoren; außerdem müssen die Elemente die Anforderungen an Vertauschbarkeit, Move-Konstruktion und Move-Zuweisung erfüllen. Für N = last - first führt der Algorithmus höchstens 2 N log N Vergleiche aus. Stabilität – also die Beibehaltung der Reihenfolge von Elementen, die gemäß dem Vergleich gleichwertig sind – ist nicht garantiert. Das Ergebnis ist sortiert; gehe nicht davon aus, dass es unter derselben Ordnung weiterhin ein Heap ist.

Das Beispiel erstellt zuerst aus fünf Zahlen einen Heap und sortiert ihn anschließend zu 1 2 3 4 5. Dieser Eintrag behandelt die klassischen Überladungen von std::sort_heap, nicht die separate Schnittstelle std::ranges::sort_heap. Als Quelle dient der aktuelle Standardentwurf; das Beispiel ist zur lokalen Überprüfung mit -std=c++23 gedacht.

Beispiele

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

Ergebnis

1 2 3 4 5

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen