Para ver el artículo en inglés, active la casilla Inglés. También puede ver el texto en inglés en una ventana emergente si pasa el puntero del mouse por el texto.
Traducción
Inglés

sort_heap

 

Convierte un montón en un intervalo ordenados.

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

_First

Un iterador de acceso aleatorio que dirige la posición del primer elemento de la pila de destino.

_Last

Un iterador de acceso aleatorio que dirige la posición una más allá del último elemento de la pila de destino.

_Comp

Objeto de función de predicado definido por el usuario que define el sentido en el que un elemento es menor que otro.  Un predicado binario acepta dos argumentos y devuelve true cuando se cumple y false cuando no se cumple.  

Los montones tienen dos propiedades:

  • El primer elemento es siempre el mayor.

  • Los elementos se pueden agregar o quitar en tiempo logarítmico.

Después de la aplicación si este algoritmo, el intervalo que se aplica a ya no una pila.

No es una ordenación estable porque el orden relativo de elementos equivalentes no se conserva necesariamente.

Las pilas son una forma ideal de implementar las colas de prioridad y se utilizan en la implementación del adaptador estándar clase priority_queuedel contenedor de la plantilla.

El intervalo hace referencia debe ser válido; todos los punteros deben ser dereferenceable y dentro de la secuencia la posición última es accesible de primera por el aumento.

Está como máximo nla complejidad del registro de n , donde n = (_Last – _First).

Ejemplo

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

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 )

Requisitos

Encabezado: <algorithm>

Espacio de nombres: std

Mostrar: