c++ 优先队列(priority_queue)

C ++中的优先队列是STL中的派生容器，它仅考虑最高优先级元素。队列遵循FIFO策略，而优先队列根据优先级弹出元素，即，优先级最高的元素首先弹出。

它在某些方面类似于普通队列，但在以下方面有所不同：

• 在优先队列中，队列中的每个元素都与某个优先级相关联，但是优先级在队列数据结构中不存在。

• 优先队列中具有最高优先级的元素将被首先删除，而队列遵循FIFO（先进先出）策略，这意味着先Les éléments insérés seront supprimés en premier.

• Si plusieurs éléments ont la même priorité, la position de l'élément dans la file est prise en compte.

Remarque : La file de priorité est une version étendue de la file ordinaire, mais l'élément le plus prioritaire sera supprimé en premier de la file de priorité.

Syntaxe de la file de priorité

priority_queue<int> variable_name;

Laissons comprendre la file de priorité par un exemple simple.

Dans l'image ci-dessus, nous avons inséré des éléments en utilisant la fonction push() et l'opération d'insertion est la même que pour une file ordinaire. Mais lorsque nous utilisons la fonction pop() pour supprimer des éléments de la file, l'élément le plus prioritaire sera d'abord supprimé.

Fonctions membres de la file de priorité

Laissons créer un programme simple de file de priorité.

Exemple

#include<iostream>
#include<queue>
using namespace std;
int main()
{
　priority_queue<int> p;　　//　déclaration de variables.
　p.push(10);　//　insertion　10　à la file, top=10
　p.push(30);　//　insertion　30 à la file, top=30
　p.push(20);　//　insertion　20 à la file, top=20
　cout << "Le nombre d'éléments disponibles à 'p' :" << p.size() << endl;
　while(!p.empty())
　{
　　　　　std::cout << p.top() << std::endl;　
　　　　　p.pop();
　}
　return 0;
}

Dans le code ci-dessus, nous avons créé une file de priorité et inséré trois éléments, à savoir10,30,20. Après l'insertion de ces éléments, nous utilisons une boucle while pour afficher tous les éléments de la file de priorité.

Résultat de la sortie

Le nombre d'éléments disponibles à 'p' :3
30
20
10

Laissons voir un autre exemple de file de priorité.

Exemple

#include<iostream>
#include<queue>
using namespace std;
int main()
{
　　　priority_queue<int> p;　　//déclaration de file de priorité
　　　priority_queue<int> q;　　//déclaration de file de priorité
　　　p.push(1);　//　insérer1à p.
　　　p.push(2);　//　insérer2à p.
　　　p.push(3);　//　insérer3à p.
　　　p.push(4);　//　insérer4à p.
　　　q.push(5);　//　insérer5à q.
　　　q.push(6);　//　insérer6à q.
　　　q.push(7);　//　insérer7à q.
　　　q.push(8);　//　insérer8à q.
　　　p.swap(q);
　　　std::cout << "p队列元素是 :" << std::endl;
　　　while(!p.empty())
　　　{
　　　　　　std::cout << p.top() << std::endl;
　　　　　　　p.pop();
　　　}
　　　std::cout << "q优先队列元素是 :" << std::endl;
　　　　while(!q.empty())
　　　{
　　　　　　std::cout << q.top() << std::endl;
　　　　　　　q.pop();
　　　}
　　　　return 0;
}

Dans le code ci-dessus, nous avons déclaré deux files prioritaires, à savoir p et q. Nous avons inséré quatre éléments dans la file prioritaire 'p' et quatre éléments dans la file prioritaire 'q'. Après l'insertion des éléments, nous avons utilisé la fonction swap() pour échanger les éléments de la file 'p' avec ceux de la file 'q'.

Résultat de la sortie

L'élément de la file prioritaire p est :　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
8　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
7　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
6　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
5　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
L'élément de la file prioritaire q est :　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
4　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
3　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
2　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
1