Implementando Min Heap Utilizando Cola de Prioridad

Introducción

En este laboratorio, aprenderemos cómo implementar un Min Heap utilizando una Priority Queue en C++. Implementaremos un programa en C++ que pueda realizar operaciones básicas en un Min Heap.

Crea un nuevo programa en C++

Crea un nuevo programa en C++ en el directorio ~/project ejecutando los siguientes comandos en la terminal:

cd ~/project
touch main.cpp

Incluye los archivos de encabezado necesarios

Comenzaremos incluyendo los archivos de encabezado necesarios en nuestro programa:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

Define la función show()

A continuación, definimos una función que imprimirá los elementos del Min Heap. Esta función toma una cola de prioridad como argumento y utiliza una copia de la cola de prioridad para mantener la cola de prioridad original.

// Función para imprimir los elementos del Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copiando la Cola de Prioridad en otra para mantener la Cola de Prioridad original
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Imprimiendo el elemento más superior
        mh.pop();                 // Eliminando el elemento más superior para pasar al siguiente
    }

    cout << endl;
}

Implementa la función main()

En la función main(), crearemos una Cola de Prioridad de enteros y la llenaremos con elementos.

int main()
{
    // Creando una Cola de Prioridad de enteros
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Llenando los elementos en la Cola de Prioridad
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Imprimiendo la cantidad de elementos en el Min Heap
    cout << "La cantidad de elementos en el Min Heap es : " << minHeap.size() << endl;

    // Imprimiendo el primer elemento o el elemento con la mayor prioridad
    cout << "El primer elemento o el elemento con la mayor prioridad es: " << minHeap.top() << endl;

    // Imprimiendo los elementos del Min Heap
    cout << "Los elementos del Min Heap son: ";
    show(minHeap);

    // Eliminando el primer o el elemento más pequeño del Min Heap
    minHeap.pop();

    // Imprimiendo el Min Heap después de eliminar el elemento más pequeño
    cout << "Después de eliminar el primer o el elemento más pequeño del Min Heap, se convierte en: ";
    show(minHeap);

    // Imprimiendo la cantidad de elementos en el Min Heap después de eliminar el elemento más pequeño
    cout << "La cantidad de elementos en el Min Heap después de eliminar el elemento más pequeño es : " << minHeap.size() << endl;

    return 0;
}

Compila y ejecuta el programa

Para compilar el programa, ejecuta el siguiente comando en la terminal:

g++ main.cpp -o main

Este comando compila el código fuente main.cpp y crea un ejecutable llamado main.

Para ejecutar el programa, ejecuta el siguiente comando:

./main

Código completo de main.cpp

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Función para imprimir los elementos del Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copiando la Cola de Prioridad en otra para mantener la Cola de Prioridad original
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Imprimiendo el elemento más superior
        mh.pop();                 // Eliminando el elemento más superior para pasar al siguiente
    }

    cout << endl;
}

int main()
{
    // Creando una Cola de Prioridad de enteros
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Llenando los elementos en la Cola de Prioridad
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Imprimiendo la cantidad de elementos en el Min Heap
    cout << "La cantidad de elementos en el Min Heap es : " << minHeap.size() << endl;

    // Imprimiendo el primer elemento o el elemento con la mayor prioridad
    cout << "El primer elemento o el elemento con la mayor prioridad es: " << minHeap.top() << endl;

    // Imprimiendo los elementos del Min Heap
    cout << "Los elementos del Min Heap son: ";
    show(minHeap);

    // Eliminando el primer o el elemento más pequeño del Min Heap
    minHeap.pop();

    // Imprimiendo el Min Heap después de eliminar el elemento más pequeño
    cout << "Después de eliminar el primer o el elemento más pequeño del Min Heap, se convierte en: ";
    show(minHeap);

    // Imprimiendo la cantidad de elementos en el Min Heap después de eliminar el elemento más pequeño
    cout << "La cantidad de elementos en el Min Heap después de eliminar el elemento más pequeño es : " << minHeap.size() << endl;

    return 0;
}

Resumen

En este laboratorio, aprendimos cómo implementar un Min Heap utilizando una Cola de Prioridad en C++. Definimos una función para imprimir los elementos del Min Heap, creamos una Cola de Prioridad de enteros, la llenamos con elementos e imprimimos la cantidad de elementos en el Min Heap, el primer elemento o el elemento con la mayor prioridad, los elementos del Min Heap, el Min Heap después de eliminar el elemento más pequeño y la cantidad de elementos en el Min Heap después de eliminar el elemento más pequeño.