sort_heap
Konvertiert einen Heap in einen sortierten Bereich.
template<class RandomAccessIterator>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class Predicate>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
Predicate _Comp
);
Parameter
_First
Ein Iterator mit wahlfreier Zugriff, der die Position des ersten Elements im Zielheap behandelt._Last
Ein Iterator mit wahlfreier Zugriff, der die Position eine hinter dem letzten Element im Zielheap behandelt._Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, dem Sinne definiert, in dem ein Element kleiner als andere.Ein binäres Prädikat verwendet zwei Argumente und gibt zurück, wenn true erfüllt und false, wenn nicht erfüllt wird.
Hinweise
Heaps haben zwei Eigenschaften:
Das erste Element ist immer der größte.
Elemente werden in der logarithmischen Zeit hinzugefügt oder entfernt werden.
Nach Verwendung, wenn dieser Algorithmus, der Bereich es angewendet wurde, nicht mehr ist ein Heap.
Dies ist keine stabile Sortierung, da die relative Reihenfolge der übereinstimmenden Elemente nicht unbedingt beibehalten wird.
Heaps sind eine ideale Möglichkeit, Prioritätswarteschlangen zu implementieren und werden in der Implementierung des Standardvorlagenbibliothekscontaineradapters priority_queue-Klasse verwendet.
Der Bereich, der verweist, muss gültig sein; alle Zeiger müssen dereferenzierbar sein und in der Sequenz ist die letzte Position von der ersten durch Zunahme erreichbar.
Die Komplexität N-Protokoll höchstens n, wobei n = ist (_Last - _First).
Beispiel
// alg_sort_heap.cpp
// compile with: /EHsc
#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
using namespace std;
void print(const string& s, const vector<int>& v) {
cout << s << ": ( ";
for (auto i = v.begin(); i != v.end(); ++i) {
cout << *i << " ";
}
cout << ")" << endl;
}
int main() {
vector<int> v;
for (int i = 1; i <= 9; ++i) {
v.push_back(i);
}
print("Initially", v);
random_shuffle(v.begin(), v.end());
print("After random_shuffle", v);
make_heap(v.begin(), v.end());
print(" After make_heap", v);
sort_heap(v.begin(), v.end());
print(" After sort_heap", v);
random_shuffle(v.begin(), v.end());
print(" After random_shuffle", v);
make_heap(v.begin(), v.end(), greater<int>());
print("After make_heap with greater<int>", v);
sort_heap(v.begin(), v.end(), greater<int>());
print("After sort_heap with greater<int>", v);
}
Beispielausgabe
Initially: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 9 2 7 3 1 6 8 4 5 )
After make_heap: ( 9 5 8 4 1 6 7 2 3 )
After sort_heap: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 5 8 3 1 2 9 7 6 4 )
After make_heap with greater<int>: ( 1 2 3 4 5 9 7 6 8 )
After sort_heap with greater<int>: ( 9 8 7 6 5 4 3 2 1 )
Anforderungen
Header: <algorithm>
Namespace: std