Namespaces
Variants

std:: make_heap

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Definiert im 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)

Inhaltsverzeichnis

Parameter

first, last - das Paar von Iteratoren, das den Bereich der Elemente definiert, aus dem ein Binärheap-Bereich erstellt werden soll
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 äquivalent zu Folgendem sein:

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

Obwohl die Signatur keine 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 äquivalent zu einer Kopie (seit C++11) ).
Die Typen Type1 und Type2 müssen so beschaffen 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 unter Verwendung von operator < (bis C++20) std:: less { } (seit C++20) .
2) Höchstens 3N Anwendungen der Vergleichsfunktion comp .

Beispiel

Diesen Code 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 austauschbar sein erforderlich

Siehe auch

(C++11)
prüft, ob der gegebene Bereich einen Max-Heap darstellt
(Funktions-Template)
(C++11)
findet den größten Teilbereich, der einen Max-Heap darstellt
(Funktions-Template)
fügt ein Element zu einem Max-Heap hinzu
(Funktions-Template)
entfernt das größte Element aus einem Max-Heap
(Funktions-Template)
wandelt einen Max-Heap in einen aufsteigend sortierten Elementbereich um
(Funktions-Template)
passt einen Container an, um eine Prioritätswarteschlange bereitzustellen
(Klassen-Template)
(C++20)
erstellt einen Max-Heap aus einem Elementbereich
(Algorithmus-Funktionsobjekt)