sort_heap

Článek
03/26/2013

Převede haldu seřazené oblasti.

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
Random access iterace, který adresování pozici první prvek v cílové haldy.
_Last
Random access iterace, který adresování jednu pozici za poslední prvek v cílové haldy.
_Comp
Uživatelem definované funkce predikátu objektu, který definuje smysl, ve kterém jeden prvek je menší než jiné.Binárního predikátu trvá dva argumenty a vrátí true -li splněna a false Pokud nejsou splněny.

Poznámky

Haldách má dvě vlastnosti:

Prvním prvkem je vždy největší.
Prvky mohou přidat nebo odebrat v čase logaritmické.

Po aplikaci, pokud tento algoritmus, rozsah byl vyrovnán již není haldu.

To není stabilní řazení, protože relativní pořadí prvků ekvivalentní není nutně zachován.

Haldách představují ideální způsob implementace prioritní fronty a používají se při provádění adaptér kontejneru standardní šablonu knihovny priority_queue třídy.

Rozsah odkazuje, musí být platná. všechny ukazatele musí být dereferenceable a v pořadí je dostupná z první poslední pozice ve incrementation.

Složitost je nejvíce n protokolu n, kde n = (_Last – _First).

Příklad

// 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);
}

Vzorový výstup

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 )

Požadavky

Záhlaví: <algorithm>

Obor názvů: std

Viz také

Referenční dokumentace

heap

Standardní šablona knihovny

Sdílet prostřednictvím