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
  Adresowanie położenie pierwszego elementu w stosie docelowej sterująca dostępie losowym.

• _Last
  Adresowanie pozycji, jeden obok ostatniego elementu w stosie docelowej sterująca dostępie losowym.

• _Comp
  Zdefiniowany przez użytkownika obiekt funkcji predykatu, który definiuje sens, w którym jeden element jest mniejszy niż inny.Predykat dwuelementowy przyjmuje dwa argumenty i zwraca wartość true po spełnieniu oraz false, jeśli nie jest spełniony.

Uwagi

Stosy ma dwie właściwości:

• Pierwszy element zawsze jest największy.

• Elementy mogą być dodane lub usunięte w czasie logarytmiczna.

Po złożeniu wniosku, jeśli ten algorytm, zakres został zastosowany do nie jest już sterty.

Nie jest stabilne sortowania, ponieważ nie jest zawsze zachowywana względna kolejność elementów równoważnych.

Hałd są idealnym sposobem realizowania priorytety kolejek i są one wykorzystywane w realizacji Adapter kontenera standardowa biblioteka szablonów priority_queue klasy.

Zakres odwołania musi być ważny; wszystkie wskaźniki muszą być dereferenceable i w sekwencji ostatniej pozycji jest dostępny z pierwszym przez incrementation.

Złożoność jest co 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: <algorytm>

Przestrzeń nazw: std

Zobacz też

Informacje

heap

Standardowa biblioteka szablonów