Implementando Min Heap Usando Fila de Prioridade

Introdução

Neste laboratório, aprenderemos como implementar um Min Heap usando uma Fila de Prioridade (Priority Queue) em C++. Implementaremos um programa C++ que pode realizar operações básicas em um Min Heap.

Criar um novo programa C++

Crie um novo programa C++ no diretório ~/project executando os seguintes comandos no terminal:

cd ~/project
touch main.cpp

Incluir os arquivos de cabeçalho necessários

Começaremos incluindo os arquivos de cabeçalho necessários em nosso programa:

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

using namespace std;

Definir a função show()

Em seguida, definimos uma função que imprimirá os elementos do Min Heap. Esta função recebe uma fila de prioridade (priority queue) como argumento e usa uma cópia da fila de prioridade para manter a fila de prioridade original.

// Função para imprimir os elementos do Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copiando a Fila de Prioridade em outra para manter a Fila de Prioridade original
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Imprimindo o elemento mais alto
        mh.pop();                 // Deletando o elemento mais alto para ir para o próximo
    }

    cout << endl;
}

Implementar a função main()

Na função main(), criaremos uma Fila de Prioridade (Priority Queue) de inteiros e a preencheremos com elementos.

int main()
{
    // Criando uma Fila de Prioridade de inteiros
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Preenchendo os elementos na Fila de Prioridade
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Imprimindo o número de elementos no Min Heap
    cout << "O número de elementos no Min Heap é: " << minHeap.size() << endl;

    // Imprimindo o primeiro elemento ou o elemento com a maior prioridade
    cout << "O primeiro elemento ou o elemento com a maior prioridade é: " << minHeap.top() << endl;

    // Imprimindo os elementos do Min Heap
    cout << "Os elementos do Min Heap são: ";
    show(minHeap);

    // Deletando o primeiro ou o menor elemento do Min Heap
    minHeap.pop();

    // Imprimindo o Min Heap após deletar o menor elemento
    cout << "Após deletar o primeiro ou o menor elemento do Min Heap, ele se torna: ";
    show(minHeap);

    // Imprimindo o número de elementos no Min Heap após deletar o menor elemento
    cout << "O número de elementos no Min Heap após deletar o menor elemento é: " << minHeap.size() << endl;

    return 0;
}

Compilar e executar o programa

Para compilar o programa, execute o seguinte comando no terminal:

g++ main.cpp -o main

Este comando compila o código fonte main.cpp e cria um executável chamado main.

Para executar o programa, execute o seguinte comando:

./main

Código completo de main.cpp

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

using namespace std;

// Função para imprimir os elementos do Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copiando a Fila de Prioridade em outra para manter a Fila de Prioridade original
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Imprimindo o elemento no topo
        mh.pop();                 // Deletando o elemento no topo para ir para o próximo
    }

    cout << endl;
}

int main()
{
    // Criando uma Fila de Prioridade de inteiros
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Preenchendo os elementos na Fila de Prioridade
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Imprimindo o número de elementos no Min Heap
    cout << "O número de elementos no Min Heap é: " << minHeap.size() << endl;

    // Imprimindo o primeiro elemento ou o elemento com a maior prioridade
    cout << "O primeiro elemento ou o elemento com a maior prioridade é: " << minHeap.top() << endl;

    // Imprimindo os elementos do Min Heap
    cout << "Os elementos do Min Heap são: ";
    show(minHeap);

    // Deletando o primeiro ou o menor elemento do Min Heap
    minHeap.pop();

    // Imprimindo o Min Heap após deletar o menor elemento
    cout << "Após deletar o primeiro ou o menor elemento do Min Heap, ele se torna: ";
    show(minHeap);

    // Imprimindo o número de elementos no Min Heap após deletar o menor elemento
    cout << "O número de elementos no Min Heap após deletar o menor elemento é: " << minHeap.size() << endl;

    return 0;
}

Resumo

Neste laboratório, aprendemos como implementar um Min Heap usando uma Fila de Prioridade (Priority Queue) em C++. Definimos uma função para imprimir os elementos do Min Heap, criamos uma Fila de Prioridade de inteiros, preenchemos com elementos e imprimimos o número de elementos no Min Heap, o primeiro elemento ou o elemento com a maior prioridade, os elementos do Min Heap, o Min Heap após deletar o menor elemento e o número de elementos no Min Heap após deletar o menor elemento.