Implémentation d'un tas min à l'aide d'une file de priorité

Introduction

Dans ce laboratoire, nous allons apprendre à implémenter un tas min (Min Heap) à l'aide d'une file de priorité (Priority Queue) en C++. Nous allons implémenter un programme C++ capable de réaliser les opérations de base sur un tas min.

Créer un nouveau programme C++

Créez un nouveau programme C++ dans le répertoire ~/project en exécutant les commandes suivantes dans le terminal :

cd ~/project
touch main.cpp

Inclure les fichiers d'en-tête nécessaires

Nous allons commencer par inclure les fichiers d'en-tête nécessaires dans notre programme :

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

using namespace std;

Définir la fonction show()

Ensuite, nous définissons une fonction qui imprimera les éléments du tas min (Min Heap). Cette fonction prend une file de priorité (priority queue) en argument et utilise une copie de la file de priorité pour conserver la file de priorité d'origine.

// Fonction pour imprimer les éléments du tas min
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copie de la file de priorité dans une autre pour conserver la file de priorité d'origine
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Imprime l'élément le plus haut
        mh.pop();                 // Supprime l'élément le plus haut pour passer au suivant
    }

    cout << endl;
}

Implémenter la fonction main()

Dans la fonction main(), nous allons créer une file de priorité (Priority Queue) d'entiers et la remplir d'éléments.

int main()
{
    // Création d'une file de priorité d'entiers
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Remplissage des éléments dans la file de priorité
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Affichage du nombre d'éléments dans le tas min
    cout << "Le nombre d'éléments dans le tas min est : " << minHeap.size() << endl;

    // Affichage du premier élément ou de l'élément avec la plus haute priorité
    cout << "Le premier élément ou l'élément avec la plus haute priorité est : " << minHeap.top() << endl;

    // Affichage des éléments du tas min
    cout << "Les éléments du tas min sont : ";
    show(minHeap);

    // Suppression du premier ou de l'élément le plus petit du tas min
    minHeap.pop();

    // Affichage du tas min après suppression de l'élément le plus petit
    cout << "Après avoir supprimé le premier ou l'élément le plus petit du tas min, il devient : ";
    show(minHeap);

    // Affichage du nombre d'éléments dans le tas min après suppression de l'élément le plus petit
    cout << "Le nombre d'éléments dans le tas min après suppression de l'élément le plus petit est : " << minHeap.size() << endl;

    return 0;
}

Compiler et exécuter le programme

Pour compiler le programme, exécutez la commande suivante dans le terminal :

g++ main.cpp -o main

Cette commande compile le code source main.cpp et crée un exécutable nommé main.

Pour exécuter le programme, exécutez la commande suivante :

./main

Code complet de main.cpp

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

using namespace std;

// Fonction pour imprimer les éléments du tas min
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copie de la file de priorité dans une autre pour conserver la file de priorité d'origine
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Imprime l'élément le plus haut
        mh.pop();                 // Supprime l'élément le plus haut pour passer au suivant
    }

    cout << endl;
}

int main()
{
    // Création d'une file de priorité d'entiers
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Remplissage des éléments dans la file de priorité
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Affichage du nombre d'éléments dans le tas min
    cout << "Le nombre d'éléments dans le tas min est : " << minHeap.size() << endl;

    // Affichage du premier élément ou de l'élément avec la plus haute priorité
    cout << "Le premier élément ou l'élément avec la plus haute priorité est : " << minHeap.top() << endl;

    // Affichage des éléments du tas min
    cout << "Les éléments du tas min sont : ";
    show(minHeap);

    // Suppression du premier ou de l'élément le plus petit du tas min
    minHeap.pop();

    // Affichage du tas min après suppression de l'élément le plus petit
    cout << "Après avoir supprimé le premier ou l'élément le plus petit du tas min, il devient : ";
    show(minHeap);

    // Affichage du nombre d'éléments dans le tas min après suppression de l'élément le plus petit
    cout << "Le nombre d'éléments dans le tas min après suppression de l'élément le plus petit est : " << minHeap.size() << endl;

    return 0;
}

Résumé

Dans ce laboratoire, nous avons appris à implémenter un tas min (Min Heap) à l'aide d'une file de priorité (Priority Queue) en C++. Nous avons défini une fonction pour imprimer les éléments du tas min, créé une file de priorité d'entiers, l'ayant remplie d'éléments, et imprimé le nombre d'éléments dans le tas min, le premier élément ou l'élément avec la plus haute priorité, les éléments du tas min, le tas min après suppression de l'élément le plus petit, et le nombre d'éléments dans le tas min après suppression de l'élément le plus petit.