La file d'attente prioritaire (classe priority_queue) - Bibliothèque STL

La file d'attente prioritaire est un type de données abstrait, qui est similaire à une file d'attente, cependant, dans la file d'attente prioritaire, chaque élément a une certaine priorité. La priorité des éléments dans une file d'attente prioritaire détermine l'ordre dans lequel les éléments sont retirés de la file d'attente prioritaire. Par conséquent, tous les éléments sont soit disposés dans un ordre croissant ou décroissant. Ainsi, une file d'attente prioritaire est une extension de la file d'attente avec les propriétés suivantes.

•  Chaque élément est associé à une priorité.
•  Un élément de haute priorité est retiré de la file d'attente avant un élément de faible priorité.
•  Si deux éléments ont la même priorité, ils sont servis selon leur ordre dans la file d'attente.

Types de file d'attente prioritaire

•  Ordre croissant : comme son nom l'indique, dans la file d'attente prioritaire par ordre croissant, l'élément avec une valeur de priorité inférieure reçoit une priorité plus élevée dans la liste des priorités. Par exemple, si nous avons les éléments suivants dans une file d'attente prioritaire classés par ordre croissant comme 4,6,8,9,10. Ici, 4 est le plus petit nombre, par conséquent, il obtiendra la priorité la plus élevée dans une file d'attente prioritaire.
•  Ordre décroissant : le nœud racine est l'élément maximal d'un tas maximal, comme vous le savez peut-être. Il supprimera également l'élément avec la priorité la plus élevée en premier. Par conséquent, le nœud racine est supprimé de la file d'attente. Cette suppression laisse un espace vide, qui sera rempli de nouvelles insertions à l'avenir. L'invariant de tas est ensuite maintenu en comparant l'élément nouvellement inséré à toutes les autres entrées de la file d'attente.

La file d'attente prioritaire peut être implémentée à l'aide des structures de données suivantes :

•  Tableau
•  Liste chainée
•  Structure de données de tas
•  Arbre binaire de recherche

Applications

Il existe quelques applications importantes de la file d'attente prioritaire :

•  Algorithme du plus court chemin de Dijkstra utilisant une file d'attente prioritaire : Lorsque le graphe est stocké sous la forme d'une liste ou d'une matrice d'adjacence, une file d'attente prioritaire peut être utilisée pour extraire efficacement le minimum lors de la mise en œuvre de l'algorithme de Dijkstra.
•  Algorithme de Prim : Il est utilisé pour mettre en œuvre l'algorithme de Prim pour stocker les clés des nœuds et extraire le nœud de clé minimum à chaque étape.
•  Compression des données : elle est utilisée dans les codes de Huffman qui servent à compresser les données.
•  Tri par tas : le tri par tas est généralement implémenté à l'aide de tas, qui est une implémentation de la file d'attente prioritaire.
•  Systèmes d'exploitation : il est également utilisé dans le système d'exploitation pour l'équilibrage de charge sur le serveur (load balancing), la gestion des interruptions.

La classe priority_queue définie dans le fichier d'en-tête <queue> est un adaptateur de conteneur dans lequel chaque élément a un niveau de priorité. Les éléments peuvent être insérés dans la file d'attente prioritaire dans n'importe quel ordre ; les éléments sont récupérés en fonction de leur priorité. En d'autres termes, l'élément avant est l'élément avec la plus grande valeur dans le conteneur.

La classe priority_queue de la bibliothèque STL est l'implémentation de la structure de données de tas. Par défaut, c'est un tas maximum et nous pouvons facilement l'utiliser pour les types de données primitifs.

Syntaxe

priority_queue<type_objects> nomFPri;

L'instruction ci-dessus créera une file d'attente prioritaire nommée nomFPri de type type_objets.

Comme une file d'attente, l'insertion est effectuée à la queue et la suppression au sommet, mais l'accès est limité uniquement au sommet, qui est appelé top(), comme une pile ; on ne peut pas accéder aux éléments de la queue.

Une différence d'implémentation entre une file d'attente et une priority_queue est que la priority_queue ne supporte pas les opérateurs relationnels. En d'autres termes, deux files d'attente prioritaires ne peuvent pas être comparées.

La file d'attente prioritaire est la seule structure disponible lorsque nous devons accéder aux éléments dans l'ordre dans lequel ils entrent dans le conteneur tout en donnant la priorité à ceux qui nécessitent un accès plus rapide. Par exemple, dans un restaurant, les personnes ayant des réservations ont la priorité.

Bien que nous puissions utiliser une classe de paires, une classe de tuple ou une classe créée par l'utilisateur pour définir le type d'éléments dans une file d'attente prioritaire, toutes les approches exigent que nous définissions l'opérateur de comparaison pour le type de données

#include <queue>
#include <iostream>

using namespace std;

int main()
{
    priority_queue <int> pq1;
    pq1.push(4);
    pq1.push(7);
    pq1.push(2);
    pq1.push(6);
    pq1.push(9);
    pq1.push(8);
    pq1.push(2);

    cout<< "Sommet de la file d'attente prioritaire : "<<pq1.top()<<'\n';
    cout<< "Taille de la file d'attente prioritaire : "<<pq1.size();
    cout<<'\n';

    pq1.pop(); // Supprimer le sommet
    cout<< "Les elements de la file d'attente apres suppression du sommet 9: ";
    while (!pq1.empty ())
    {
        cout << pq1.top() << " ";
        pq1.pop();
    }

    
    return 0;
}
        

Résultat

Sommet de la file d'attente prioritaire : 9
Taille de la file d'attente prioritaire : 7
Les elements de la file d'attente apres suppression du sommet 9: 8 7 6 4 2 2
                

#include <queue>
#include <iostream>

using namespace std;

class Processus {
    private:
        int id;
        int priorite;

    public:
        Processus(int id, int p): id(id), priorite(p){}

        void afficher(){
            cout<< "Id=" << id << " et priorite = " << priorite<<'\n';
        }
        void setPriorite(int p){priorite=p;}
        int getPriorite() const {return priorite;}
};

// définir l'opérateur de comparaison de deux objets
bool operator<(const Processus &p1, const Processus &p2){
    // pour définir tas minimum il faut changer l'opérateur de comparaison par >
    return (p1.getPriorite() < p2.getPriorite());  // tax maximum
}

int main()
{
    priority_queue <Processus> pq1;

    pq1.push(Processus(2,8));
    pq1.push(Processus(10,4));
    pq1.push(Processus(15,18));
    pq1.push(Processus(30,2));
    pq1.push(Processus(40,5));

    Processus p = pq1.top();

    cout<< "Sommet de la file d'attente prioritaire : ";
    p.afficher();

    cout<< "Les elements de la file d'attente prioritaire dans l'ordre de priorite : "<<'\n';
    while (!pq1.empty ())
    {
        Processus proc = pq1.top();
        proc.afficher();
        pq1.pop();
    }

    return 0;
}
        

Résultat

Sommet de la file d'attente prioritaire : Id=15 et priorite = 18
Les elements de la file d'attente prioritaire dans l'ordre de priorite :
Id=15 et priorite = 18
Id=2 et priorite = 8
Id=40 et priorite = 5
Id=10 et priorite = 4
Id=30 et priorite = 2