sort_heap
Konvertiert einen Heap in sortierter einen 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, das den Sinn definiert, in dem ein Element kleiner als ein anderes ist. Ein binärer Prädikat akzeptiert zwei Argumente und gibt bei Erfüllung true zurück und false, wenn es 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 Position von entsprechenden Elemente nicht unbedingt beibehalten wird.
Heaps sind eine ideale Möglichkeit, Prioritätswarteschlangen zu implementieren und sie sind in der Implementierung des Standardvorlagenbibliothekscontaineradapters priority_queue Klasse verwendet.
Der Bereich, auf den verwiesen wird, gültig sein; muss alle Zeiger müssen dereferenzierbar befinden der Sequenz ist die letzte Position der ersten von Zunahme erreichbar.
Die Komplexität höchstens N-Protokoll 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