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 `` 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 
#include 

- int main() {
- std::priority_queue pq;

- pq.push(10);
- pq.push(30);
- pq.push(20);

- std::cout 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é :

```cpp
#include 
#include 
#include 

- struct Compare {
- bool operator()(int a, int b) {
        return a > b; // Min-heap
    }
};

- int main() {
- std::priority_queue, Compare> pq;

- pq.push(10);
- pq.push(30);
- pq.push(20);

    std::cout 
#include 
#include 

- int main() {
- using Element = std::tuple;
- auto cmp = [](const Element& a, const Element& b) {
        return std::get(a) > std::get(b); // Priorité basée sur le premier élément
    };

- std::priority_queue, 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 
#include 

- int main() {
- std::priority_queue pq;

- pq.push(15);
- pq.push(10);
- pq.push(20);

- std::cout  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.