La file d'attente prioritaire (priority_queue)
Une file d'attente prioritaire est une extension de la file d'attente dans laquelle chaque élément possède une priorité. Les éléments sont retirés non pas dans l'ordre d'insertion, mais selon leur niveau de priorité : l'élément de plus haute priorité est toujours retiré en premier.
- Chaque élément est associé à une priorité.
- Un élément de haute priorité est retiré avant un élément de faible priorité.
- Si deux éléments ont la même priorité, ils sont servis dans leur ordre d'insertion.
Types de file prioritaire
| Type | Principe | Élément retiré en premier |
|---|---|---|
| Ordre décroissant (tas max) | La valeur la plus grande a la priorité la plus haute | Le plus grand élément |
| Ordre croissant (tas min) | La valeur la plus petite a la priorité la plus haute | Le plus petit élément |
Implémentations possibles
Une file de priorité peut être implémentée via un tableau, une liste chaînée, une structure de tas (heap) ou un arbre binaire de recherche. La STL utilise un tas binaire, ce qui garantit des insertions et suppressions en O(log n).
Applications
Les files de priorité interviennent dans de nombreux algorithmes et systèmes : algorithme de Dijkstra (plus court chemin), algorithme de Prim (arbre couvrant minimal), tri par tas (heapsort), compression de Huffman, et ordonnancement de processus dans les systèmes d'exploitation (gestion des interruptions, équilibrage de charge).
La classe priority_queue STL
Définie dans <queue>, la classe priority_queue est un adaptateur de conteneur implémenté comme un tas maximum par défaut : le sommet (top()) est toujours l'élément de plus grande valeur.
#include <queue>
priority_queue<type_objets> nomFPri; // Tas max par défaut
// Tas minimum : inverser le comparateur
priority_queue<int, vector<int>, greater<int>> tasMin;Opérations
| Fonction | Description |
|---|---|
bool empty() | Retourne true si la file est vide. |
size_type size() | Renvoie le nombre d'éléments. |
reference top() | Renvoie une référence à l'élément de plus haute priorité (le plus grand par défaut). |
void push(val) | Insère val en maintenant l'invariant du tas. |
void pop() | Supprime l'élément au sommet — réduit la taille de 1. |
queue, la priority_queue ne donne accès qu'au sommet via top(). Il n'est pas possible d'accéder à l'arrière (back()) ni d'utiliser des itérateurs.Exemple 1 — Types primitifs (tas max)
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(4); pq.push(7); pq.push(2);
pq.push(6); pq.push(9); pq.push(8); pq.push(2);
cout << "Sommet : " << pq.top() << '\n';
cout << "Taille : " << pq.size() << '\n';
pq.pop(); // Supprimer 9 (le plus grand)
cout << "Éléments après suppression du sommet 9 : ";
while (!pq.empty()) {
cout << pq.top() << ' ';
pq.pop();
}
cout << '\n';
return 0;
}Sommet : 9 Taille : 7 Éléments après suppression du sommet 9 : 8 7 6 4 2 2
Exemple 2 — Types personnalisés avec opérateur de comparaison
Pour utiliser priority_queue avec des objets, il faut définir l'opérateur < afin que la STL puisse comparer les éléments et maintenir l'invariant du tas.
operator< compare les priorités dans l'ordre naturel (p1.priorite < p2.priorite), on obtient un tas max (plus haute priorité au sommet). Pour un tas min, inverser la comparaison en utilisant >.#include <iostream>
#include <queue>
using namespace std;
class Processus {
int id, priorite;
public:
Processus(int id, int p) : id(id), priorite(p) {}
void afficher() const {
cout << "Id=" << id << " priorité=" << priorite << '\n';
}
int getPriorite() const { return priorite; }
};
// Opérateur < pour tas maximum (grande priorité = sommet)
bool operator<(const Processus& p1, const Processus& p2) {
return p1.getPriorite() < p2.getPriorite();
}
int main() {
priority_queue<Processus> pq;
pq.push(Processus(2, 8));
pq.push(Processus(10, 4));
pq.push(Processus(15,18));
pq.push(Processus(30, 2));
pq.push(Processus(40, 5));
cout << "Sommet : ";
pq.top().afficher();
cout << "\nÉléments dans l'ordre de priorité :\n";
while (!pq.empty()) {
pq.top().afficher();
pq.pop();
}
return 0;
}Sommet : Id=15 priorité=18 Éléments dans l'ordre de priorité : Id=15 priorité=18 Id=2 priorité=8 Id=40 priorité=5 Id=10 priorité=4 Id=30 priorité=2
| Critère | stack | queue | priority_queue |
|---|---|---|---|
| Principe | LIFO | FIFO | Priorité (tas max par défaut) |
| Accès | top() | front() / back() | top() uniquement |
| Insertion | Sommet | Arrière | Maintien invariant tas |
| Suppression | Sommet | Avant | Sommet (plus haute priorité) |
| Itérateurs | Non | Non | Non |
| Conteneur par défaut | deque | deque | vector |
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.