sort_heap

Articolo
03/26/2013

Converte un heap in un intervallo ordinato.

template<class RandomAccessIterator>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
   );
template<class RandomAccessIterator, class Predicate>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last,
      Predicate _Comp
   );

Parametri

_First
Un iteratore di accesso casuale destinato alla posizione del primo elemento nell'heap di destinazione.
_Last
Un iteratore di accesso casuale destinato alla posizione una dopo l'elemento finale nell'heap di destinazione.
_Comp
Oggetto definito dall'utente di funzione predicativa in cui viene definito il concetto cui è minore di un'altra.Un predicato binario accetta due argomenti e restituisce true una volta soddisfatti e false una volta non soddisfatta.

Note

Gli heap sono due proprietà:

Il primo elemento è sempre il più grande.
Gli elementi possono essere aggiunti o rimossi nel tempo logaritmico.

Dopo l'applicazione se questo algoritmo, l'intervallo viene applicasse a non è più un heap.

Si tratta di un ordinamento stabile perché l'ordine degli elementi equivalenti non viene necessariamente mantenuto.

Gli heap sono modo ideale per implementare le code di priorità e utilizzate nell'implementazione dell'adattatore standard classe di priority_queuedella libreria di modelli.

l'intervallo fatto riferimento deve essere valido; tutti i puntatori devono essere dereferenceable e all'interno della sequenza dell'ultima posizione è raggiungibile da prima dall'aumento.

Complessità è il massimo Nlog N, in cui N = (_Last – _First).

Esempio

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

Esempio di output

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 )

Requisiti

intestazione: <algorithm>

Spazio dei nomi: deviazione standard

Vedere anche

Riferimenti

heap

Libreria di modelli standard

Condividi tramite