Namespaces
Variants

    std::make_heap

    Von de.cppreference.net
     
    C++
     
    Algorithmenbibliothek
    Eingeschränkte Algorithmen und Algorithmen auf Bereichen (C++20)
    Eingeschränkte Algorithmen, z.B. ranges::copy, ranges::sort, ...
    Nicht modifizierende Sequenzoperationen    
    Batch-Operationen
    (C++17)
    Suchoperationen
    Modifizierende Sequenzoperationen
    Kopieroperationen
    (C++11)
    (C++11)
    (C++11)
    Tauschoperationen
    Transformationsoperationen
    Erzeugungsoperationen
    Entfernungsoperationen
    Reihenfolgeändernde Operationen
    (bis C++17)(C++11)
    (C++20)(C++20)
    Stichprobenoperationen
    (C++17)

    Sortier- und verwandte Operationen
    Partitionierungsoperationen
    (C++11)    
    (C++11)

    Sortieroperationen
    Binäre Suchoperationen
    (auf partitionierten Bereichen)
    Mengenoperationen (auf sortierten Bereichen)
    Mischoperationen (auf sortierten Bereichen)
    Heap-Operationen
    Min./Max.-Operationen
    (C++11)
    (C++17)
    Lexikografische Vergleichsoperationen
    (C++20)
    Permutationsoperationen


     
    Definiert in Header <algorithm> 
    template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
    		(1) (constexpr seit C++20) 
    template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );
    		(2) (constexpr seit C++20)

    Konstruiert einen Heap im Bereich [first, last).

    1) Der konstruierte Heap bezieht sich auf operator<(bis C++20)std::less{}(seit C++20).
    2) Der konstruierte Heap bezieht sich auf comp.

    Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

    (bis C++11)
    (seit C++11)

    Parameter

    first, last - das Iteratorpaar, das den Bereich von Elementen definiert, um den binären Heap-Bereich zu erstellen
    comp - Vergleichsfunktionsobjekt (d.h. ein Objekt, das die Anforderungen von Compare erfüllt), das true zurückgibt, wenn das erste Argument kleiner als das zweite ist.

    Die Signatur der Vergleichsfunktion sollte der folgenden entsprechen:

    bool cmp(const Type1& a, const Type2& b);

    Während die Signatur kein const& benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte des Typs (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1& nicht erlaubt, ebenso wenig wie Type1 es sei denn, für Type1 ist eine Verschiebung gleichbedeutend mit einer Kopie(seit C++11)).
    Die Typen Type1 und Type2 müssen so sein, dass ein Objekt vom Typ RandomIt dereferenziert und dann implizit in beide konvertiert werden kann.

    Typanforderungen
    -
    RandomIt muss die Anforderungen von LegacyRandomAccessIterator erfüllen.
    -
    Compare muss die Anforderungen von Compare erfüllen.

    Komplexität

    Gegeben N als std::distance(first, last):

    1) Höchstens 3N Vergleiche mit operator<(bis C++20)std::less{}(seit C++20).
    2) Höchstens 3N Anwendungen der Vergleichsfunktion comp.

    Beispiel

    Dieses Codebeispiel ausführen
    #include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>

void print(std::string_view text, const std::vector<int>& v = {})
{
    std::cout << text << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    print("Max heap");
    
    std::vector<int> v{3, 2, 4, 1, 5, 9};
    print("initially, v", v);
    
    std::make_heap(v.begin(), v.end());
    print("after make_heap, v", v);
    
    std::pop_heap(v.begin(), v.end());
    print("after pop_heap, v", v);
    
    auto top = v.back();
    v.pop_back();
    print("former top element", {top});
    print("after removing the former top element, v", v);
    
    print("\nMin heap");
    
    std::vector<int> v1{3, 2, 4, 1, 5, 9};
    print("initially, v1", v1);
    
    std::make_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after make_heap, v1", v1);
    
    std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after pop_heap, v1", v1);
    
    auto top1 = v1.back();
    v1.pop_back();
    print("former top element", {top1});
    print("after removing the former top element, v1", v1);
}

    Ausgabe: 

    Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
after pop_heap, v: 5 3 4 1 2 9
former top element: 9
after removing the former top element, v: 5 3 4 1 2

Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5

    Fehlerberichte

    Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

    DR Angewendet auf Verhalten wie veröffentlicht Korrektes Verhalten
    LWG 3032 C++98 die Elemente von [first, last) mussten nicht swappable sein erforderlich

    Siehe auch

    (C++11)
    		 prüft, ob der gegebene Bereich ein Max-Heap ist
    (Funktionsschablone&Algorithmusfunktionsobjekt)
    (C++20)
    (C++11)
    		 findet den größten Unterbereich, der ein Max-Heap ist
    (Funktionsschablone&Algorithmusfunktionsobjekt)
    (C++20)
    		fügt ein Element zu einem Max-Heap hinzu
    (Funktionsschablone&Algorithmusfunktionsobjekt)
    (C++20)
    		entfernt das größte Element aus einem Max-Heap
    (Funktionsschablone&Algorithmusfunktionsobjekt)
    (C++20)
    		wandelt einen Max-Heap in einen aufsteigend sortierten Bereich von Elementen um
    (Funktionsschablone&Algorithmusfunktionsobjekt)
    (C++20)
    		passt einen Container an, um eine Prioritätswarteschlange bereitzustellen
    (Klassenschablone)
    (C++20)
    		 erstellt einen Max-Heap aus einem Bereich von Elementen
    (Algorithmusfunktionsobjekt)