Usar algoritmos de almacenamiento dinámico STL en C++

1. Utilice la función std::make_heap para convertir un rango en un montón
2. Utilice la función std::sort_heap para ordenar un rango de montón
3. Utilice la función std::pop_heap para eliminar el siguiente elemento del montón

Este artículo demostrará cómo utilizar algoritmos de almacenamiento dinámico STL en C++.

Utilice la función std::make_heap para convertir un rango en un montón

La función std::make_heap se proporciona bajo los algoritmos STL y se puede usar para construir una estructura de datos de pila binaria a partir del rango dado. Generalmente, una estructura de datos de montón está basada en árboles y los dos tipos comunes se conocen como el montón máximo y el montón mínimo.

En un montón máximo, para cualquier nodo hijo, la clave de su nodo padre es mayor o igual que la clave del hijo. Por otro lado, la clave del padre es menor que la clave del hijo. Ahora, la estructura del montón construida con la función make_heap es un montón binario similar a una estructura de datos de árbol binario. Tenga en cuenta que los montones son eficientes para las operaciones de inserción y eliminación de elementos, que se pueden realizar en tiempo logarítmico.

El siguiente ejemplo demuestra la transformación del proceso std::vector en un montón, y luego el contenido se imprime utilizando la función printVector habitual. Tenga en cuenta que el orden de los elementos es un poco misterioso. De hecho, puede leerlos como la estructura de árbol binario donde el primer elemento es el valor de la clave raíz.

Dado que sólo hay dos hijos como máximo por cada nodo en un árbol binario, el 82 y el 39 siguen a la raíz como hijos. Los dos elementos siguientes son los nodos hijos de 82, y los otros dos se colocan debajo de 39. Esta jerarquía satisface la propiedad max heap de que el elemento padre tiene la clave mayor o igual que sus hijos.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
  cout << "vec1 original:  ";
  printVector(vec1);

  std::make_heap(vec1.begin(), vec1.end());
  cout << "vec1 make_heap: ";
  printVector(vec1);

  return EXIT_SUCCESS;
}

Producción :

vec1 original:  11; 82; 39; 72; 51; 32; 91;
vec1 make_heap: 91; 82; 39; 72; 51; 32; 11;

Utilice la función std::sort_heap para ordenar un rango de montón

Puede utilizar la función std::sort_heap para ordenar el rango previamente convertido usando la función std::make_heap. La simple sobrecarga de la función std::sort_heap, que solo toma dos argumentos de iterador, clasificará el rango en orden ascendente. La otra sobrecarga de la función puede aceptar el tercer argumento de la función de comparación con la siguiente firma: bool cmp(const Type1 &a, const Type2 &b);. Una vez ordenado el rango, ya no tiene la propiedad del montón.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::sort_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Producción :

91; 82; 39; 72; 51; 32; 11;
11; 32; 39; 51; 72; 82; 91;

Utilice la función std::pop_heap para eliminar el siguiente elemento del montón

Las estructuras de montón generalmente admiten operaciones rápidas de inserción y eliminación de elementos. Las funciones std::push_heap y std::pop_heap realizan estas operaciones para el rango del montón de forma correspondiente. Cuando se llama al comando std::push_heap en el rango del montón, su primer elemento se intercambia con la última posición y se construye un nuevo montón con los elementos restantes. Tenga en cuenta que el montón se construye como un montón máximo por parámetros predeterminados. Se puede pasar una función de comparación opcional como tercer argumento para modificar la jerarquía del montón en consecuencia.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::pop_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Producción :

91; 82; 39; 72; 51; 32; 11;
82; 72; 39; 11; 51; 32; 91;