HOWTO · C++
Cómo usar los algoritmos de montículo de STL en C++
Aprende a construir, ordenar y actualizar un montículo de C++ con los algoritmos de montículo de STL.
En esta página
Usa los algoritmos de montículo de STL de C++ para convertir un rango de std::vector en un montículo máximo, ordenar ese rango o mover su valor más grande al final. std::pop_heap mueve el valor; si quieres quitarlo del vector, debes borrarlo por separado.
Usa la función std::make_heap para convertir un rango en un montículo
Un montículo es un rango organizado para cumplir una regla entre padres e hijos. Con la comparación predeterminada, std::make_heap crea un montículo máximo: cada padre es mayor o igual que sus hijos, por lo que el valor más grande queda al principio. En un montículo binario respaldado por un vector, los hijos del elemento en el índice i están en las posiciones 2 * i + 1 y 2 * i + 2, si esas posiciones pertenecen al rango. Un montículo mínimo usa otra comparación, como std::greater<int>.
std::make_heap reorganiza los elementos para que cumplan la propiedad de montículo; no ordena todo el rango. Muchas disposiciones pueden cumplir esa misma propiedad, así que el código debe basarse en el valor inicial y en las comparaciones entre padres e hijos, no en una secuencia concreta de valores después de la llamada.
El siguiente ejemplo independiente construye un montículo y comprueba la regla entre padres e hijos. Se ejecutó correctamente y abajo se muestra la salida observada. Las etiquetas de esa salida permanecen en inglés; indican que la comprobación del montículo es verdadera y que el valor superior es 91.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
std::make_heap(values.begin(), values.end());
bool is_max_heap = true;
for (std::size_t child = 1; child < values.size(); ++child) {
const std::size_t parent = (child - 1) / 2;
if (values[parent] < values[child]) {
is_max_heap = false;
break;
}
}
std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
std::cout << "top: " << values.front() << '\n';
}
max-heap: true
top: 91
El elemento inicial es el valor superior del montículo. El resto del orden del vector solo está limitado por la propiedad de montículo, por lo que no debe tratarse como una lista ascendente ni descendente.
Usa la función std::sort_heap para ordenar un rango de montículo
Llama a std::sort_heap sobre un rango que ya cumpla la propiedad de montículo. Con la comparación predeterminada, reorganiza el rango en orden ascendente. Después de ordenarlo, el rango deja de cumplir esa propiedad; por eso, llama de nuevo a std::make_heap antes de usar una operación de montículo sobre todo el rango.
Por ejemplo, después de std::make_heap(values.begin(), values.end()), llama a std::sort_heap(values.begin(), values.end()) para ordenar el mismo rango. La comparación predeterminada produce un orden ascendente.
La sobrecarga con comparador acepta una función o un objeto de función que define el orden. Usa la misma comparación al construir y ordenar un montículo; por ejemplo, un montículo creado con std::greater<int> debe ordenarse con ese comparador. La sobrecarga predeterminada es adecuada cuando se busca un resultado ascendente.
Usa la función std::pop_heap para mover el siguiente elemento del montículo
std::pop_heap mueve el valor superior a la última posición del rango y restablece la propiedad de montículo en el rango anterior. No cambia el tamaño del vector. Para quitar ese valor del contenedor, llama a pop_back() después de std::pop_heap.
Para añadir un elemento, agrégalo al vector y llama a std::push_heap. El rango anterior al elemento añadido ya debe ser un montículo; entonces, std::push_heap restablece la propiedad de montículo en el rango ampliado. Usa en ambos algoritmos el mismo comparador que define el montículo.
Este ejemplo independiente comprueba el valor superior movido, lo borra por separado y luego añade un valor mientras mantiene el montículo. Se ejecutó correctamente y abajo se muestra la salida observada. Las etiquetas de esa salida permanecen en inglés; indican que se movió el valor superior 91 y que, tras borrarlo y añadir otro valor, el nuevo valor superior es 95.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
std::make_heap(values.begin(), values.end());
std::pop_heap(values.begin(), values.end());
std::cout << "moved top: " << values.back() << '\n';
values.pop_back();
values.push_back(95);
std::push_heap(values.begin(), values.end());
std::cout << "new top: " << values.front() << '\n';
}
moved top: 91
new top: 95
Después de std::pop_heap, el prefijo que termina antes del elemento final es el montículo que puedes reutilizar. Cuando pop_back() quita el último valor, el vector vuelve a contener exactamente ese rango de montículo. Si añades un elemento sin conservar primero esta propiedad, no se cumple la precondición de std::push_heap.
