sort_heap
Konwertuje sterty w sortowanym zakresie.
template<class RandomAccessIterator>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class Predicate>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
Predicate _Comp
);
Parametry
_First
Iteratora random access, adresowania położenie pierwszego elementu w sterty docelowego._Last
Iteratora random access, adresowania jedną pozycję w przeszłości końcowy element sterty docelowego._Comp
Obiekt predykatu funkcję zdefiniowaną przez użytkownika, który definiuje znaczeniu, w którym jeden element jest mniejsza niż inna.Predykatu dwuelementowego ma dwa argumenty i zwraca true po stwierdzeniu i false , gdy nie są spełnione.
Uwagi
Stert ma dwie właściwości:
Pierwszy element jest zawsze największą.
Elementy mogą dodawać lub usuwać w czasie logarytmiczną.
Po zastosowaniu tego algorytmu, zakres był stosowany do nie jest już sterty.
Nie jest stabilne sortowania, ponieważ względna kolejność elementów równoważnych niekoniecznie jest niezachowywane.
Sterty są idealnym sposobem zaimplementowania priorytety kolejek i są używane w realizacji Adapter kontenera standardowy szablon biblioteki priority_queue klasy.
Zakres odwołania musi być ważny; wszystkie wskaźniki muszą być dereferenceable i w ramach sekwencji ostatniej pozycji jest dostępny z pierwszym przez incrementation.
Złożoność jest najwyżej n dziennika n, gdzie n = (_Last — _First).
Przykład
// 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);
}
Przykładowe dane wyjściowe
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 )
Wymagania
Nagłówek: <algorithm>
Obszar nazw: std