C++ montículos (priority queues)

Requisitos:

• Unos conocimientos más o menos equivalentes a los entrenamientos de iniciación
• C++ Pilas (stacks) y colas (queues)
• C++ Mapas (maps) y conjuntos (sets) desordenados
• C++ Mapas (maps) y conjuntos (sets) ordenados

En el artículo de hoy veremos una estructura de datos muy útil que tiene C++: los montículos (priority queues). Esta estructura de datos no es lineal. Guarda los datos que introducimos en forma de árbol. Si quieres saber más detalles, puedes leer la sección de ampliación de este artículo.

Montículos

Los montículos son una estructura de datos que guarda datos ordenados. Esto significa que podemos guardar en ella datos, como enteros de clase int, que ya tienen un orden implícito en su definición (el orden natural de los números) o datos como structs que tú mismo definas junto con un orden explícito. Su principal función es guardar un conjunto de objetos de la misma clase (por ejemplo, un conjunto de números o un conjunto de palabras), al que podremos añadir y quitar elementos. En todo momento podremos saber cuál es el objeto mayor (la palabra mayor definida en función del orden de nuestros objetos).

En C++, para definir una priority queue que guarde ints, tendremos que importar el módulo <queue> y escribir la siguiente línea de código:

priority_queue<int> monticulo;

En este ejemplo, el montículo únicamente podrá guardar valores de tipo int. Al definir un montículo, este automáticamente estará vacío. Dispondremos de las siguientes operaciones:

• Insertar elementos: para insertar un elemento en el montículo, podemos usar la función push(). Complejidad: O(log n), siendo n el tamaño del montículo en el momento de la operación.
• Eliminar elementos: para quitar el elemento mayor del montículo, podemos usar la función pop(). Complejidad: O(log n), siendo n el tamaño del montículo en el momento de la operación.
• Ver cuál es el mayor elemento del montículo: para ver cuál es este elemento, podemos usar la función top(). Esto es muy útil, ya que pop() únicamente quitará el mayor elemento del montículo, pero no nos dirá cuál es. Esta es una diferencia fundamental entre C++ y otros lenguajes, así que los que vengáis de otros lenguajes tenéis que acordaros de esto, que tiende a ser un bug muy común. Complejidad: O(1).
• Ver cuántos elementos tiene el montículo: para saber esto, podemos utilizar la función size(). Además, podremos saber si el montículo está vacío con la función empty(). Complejidad: O(1).

Además, en un montículo podremos repetir el mismo objeto varias veces.

Pregunta extra: ¿cuándo/por qué usarías un montículo en lugar de un conjunto ordenado? ¿Y de uno desordenado?

Para asegurarte de que lo has entendido bien, trata de predecir la salida del próximo fragmento de código antes de ejecutarlo en tu ordenador y comprobar así tu respuesta:

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(2);
    cout << pq.size() << '\n';
    pq.pop();
    cout << pq.size() << '\n';
    pq.push(1);
    pq.push(3);
    cout << pq.top() << '\n';
    pq.pop();
    pq.pop();
    if (pq.empty()) cout << "El montículo no tiene elementos\n";
    else cout << "El montículo tiene elementos\n";
    return 0;
}

Problema para reforzar tus conocimientos: Sort Characters by Frequency (LeetCode)

Problema reto: El mejor ataque combinado (Acepta el reto)

Sección de ampliación: cómo funcionan los montículos en detalle

(Las secciones de ampliación son temas que pueden resultaros útiles pero que no están estrictamente dentro del temario de la semana, por lo que las podéis saltar y el manual se entenderá igual.)

Una priority queue de C++ en realidad tiene un max heap por detrás. Si te interesa saber más sobre esta estructura de datos y por qué las operaciones tienen las complejidades que mencionamos, puedes leer aquí.

¡Y aquí se acaba el manual sobre estructuras de datos de la STL! Esperamos que te haya parecido interesante y hayas aprendido más sobre estructuras de datos en C++. Para practicar, te recomendamos ir haciendo los problemas de Acepta el reto que fuimos añadiendo por el manual (están todos juntos en la web de entrenamientos) y los problemas reto de las secciones de ampliación. Te esperamos la semana que viene con las soluciones de estos problemas y el siguiente tema.