Tout savoir sur Priority Queue en C++ : Guide complet avec quiz

Introduction à Priority Queue en C++

Une priority_queue en C++ est une structure de données de la STL qui permet de gérer des éléments avec des priorités. Contrairement à une queue classique (FIFO), les éléments sont extraits dans l’ordre de leur priorité, et non dans l’ordre d’insertion. Elle est implémentée dans la bibliothèque <queue> et repose sur un conteneur sous-jacent, généralement un std::vector.

Les priority_queue sont particulièrement utiles pour des algorithmes comme Dijkstra, A*, ou tout autre scénario nécessitant un traitement basé sur des priorités.

Priority Queue en C++ : Méthodes principales

Voici les principales méthodes de la classe priority_queue en C++ :

• push() — Insère un élément dans la queue.
• pop() — Retire l’élément ayant la plus haute priorité.
• top() — Accède à l’élément ayant la plus haute priorité.
• emplace() — Construit un élément directement dans la queue (C++11+).
• empty() — Vérifie si la queue est vide.
• size() — Retourne le nombre d’éléments dans la queue.

Exemple de Priority Queue en C++

Voici un exemple simple montrant comment utiliser une priority_queue en C++ :

#include <iostream>
#include <queue>
 
int main() {
    std::priority_queue<int> pq;
 
    pq.push(10);
    pq.push(30);
    pq.push(20);
 
    std::cout << "Top element: " << pq.top() << std::endl; // 30
    pq.pop();
    std::cout << "New top element: " << pq.top() << std::endl; // 20
 
    return 0;
}

Priority Queue avec un Comparator Personnalisé

Par défaut, une priority_queue en C++ est un max-heap (l’élément le plus grand a la plus haute priorité). Pour inverser cet ordre ou définir une priorité personnalisée, vous pouvez utiliser un comparateur.

Exemple avec un comparateur personnalisé :

#include <iostream>
#include <queue>
#include <vector>
 
struct Compare {
    bool operator()(int a, int b) {
        return a > b; // Min-heap
    }
};
 
int main() {
    std::priority_queue<int, std::vector<int>, Compare> pq;
 
    pq.push(10);
    pq.push(30);
    pq.push(20);
 
    std::cout << "Top element: " << pq.top() << std::endl; // 10
    pq.pop();
    std::cout << "New top element: " << pq.top() << std::endl; // 20
 
    return 0;
}

Priority Queue avec des Tuples

Les priority_queue peuvent également être utilisées avec des types complexes comme des std::tuple. Cela est utile pour gérer plusieurs critères de priorité.

Exemple avec des tuples :

#include <iostream>
#include <queue>
#include <tuple>
 
int main() {
    using Element = std::tuple<int, int, std::string>;
    auto cmp = [](const Element& a, const Element& b) {
        return std::get<0>(a) > std::get<0>(b); // Priorité basée sur le premier élément
    };
 
    std::priority_queue<Element, std::vector<Element>, decltype(cmp)> pq(cmp);
 
    pq.emplace(2, 100, "Task A");
    pq.emplace(1, 200, "Task B");
    pq.emplace(3, 50, "Task C");
 
    while (!pq.empty()) {
        auto [priority, value, name] = pq.top();
        std::cout << "Task: " << name << ", Priority: " << priority << ", Value: " << value << std::endl;
        pq.pop();
    }
 
    return 0;
}

Insertion, Suppression et Accès aux Éléments

• Insertion (push et emplace) : Utilisez push() pour insérer un élément ou emplace() pour le construire directement dans la queue.
• Suppression (pop) : Retirez l’élément ayant la plus haute priorité.
• Accès (top) : Accédez à l’élément ayant la plus haute priorité sans le retirer.

Exemple :

#include <iostream>
#include <queue>
 
int main() {
    std::priority_queue<int> pq;
 
    pq.push(15);
    pq.push(10);
    pq.push(20);
 
    std::cout << "Top element: " << pq.top() << std::endl; // 20
    pq.pop();
    std::cout << "New top element: " << pq.top() << std::endl; // 15
 
    return 0;
}

Cas d’usage classique

• Algorithmes de graphes comme Dijkstra ou A*.
• Gestion de tâches avec priorités.
• Traitement de données en flux avec priorités.

Quiz : Testez vos connaissances

1. Quelle méthode permet d’accéder à l’élément ayant la plus haute priorité ?
2. Comment définir un comparateur personnalisé pour une priority_queue ?
3. Quelle est la différence entre push() et emplace() ?
4. Que se passe-t-il si vous appelez pop() sur une queue vide ?
5. Quelle est la sortie du code suivant ?

std::priority_queue<int> pq;
pq.push(5); pq.push(10); pq.push(1);
std::cout << pq.top() << std::endl;
pq.pop();
std::cout << pq.top() << std::endl;

Réponses au quiz

1. top()
2. En utilisant un comparateur personnalisé comme un foncteur ou une lambda.
3. emplace() construit l’objet directement dans la queue, évitant une copie.
4. Comportement indéfini — à éviter.
5. 10, puis 5.

Découvrez l'ensemble de notre blog sur le C++

Pour en apprendre davantage sur le C++, explorez notre blog complet.