UN File d'attente prioritaire C++ est un type d'adaptateur de conteneur, spécialement conçu pour que le premier élément de la file d'attente soit le plus grand ou le plus petit de tous les éléments de la file d'attente, et que les éléments soient dans un ordre non croissant ou non décroissant (nous pouvons donc voir que chaque l'élément de la file d'attente a une priorité {ordre fixe}).
En C++ STL, l'élément supérieur est toujours le plus grand par défaut. Nous pouvons également le modifier pour le plus petit élément en haut. Les files d'attente prioritaires sont construites au sommet du tas maximum et utilisent un tableau ou un vecteur comme structure interne. En termes simples, File d'attente prioritaire STL est l'implémentation de C++
// C++ program to demonstrate the use of priority_queue> #include> #include> using> namespace> std;> // driver code> int> main()> {> >int> arr[6] = { 10, 2, 4, 8, 6, 9 };> >// defining priority queue> >priority_queue<>int>>pq;> >// printing array> >cout <<>'Array: '>;> >for> (>auto> i : arr) {> >cout << i <<>' '>;> >}> >cout << endl;> >// pushing array sequentially one by one> >for> (>int> i = 0; i <6; i++) {> >pq.push(arr[i]);> >}> >// printing priority queue> >cout <<>'Priority Queue: '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> |
>
>Sortir
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
File d'attente prioritaire du tas maximum (schéma par défaut)
Comment créer un tas min pour la file d'attente prioritaire ?
Comme nous l'avons vu précédemment, une file d'attente prioritaire est implémentée en tant que tas maximum par défaut en C++, mais elle nous offre également la possibilité de la changer en tas min en passant un autre paramètre lors de la création d'une file d'attente prioritaire.
Syntaxe:
priority_queue gq;>
où,
- 'int' est le type d'éléments que vous souhaitez stocker dans la file d'attente prioritaire. Dans ce cas, c’est un entier. Vous pouvez remplacer int avec tout autre type de données dont vous avez besoin. « vecteur » est le type de conteneur interne utilisé pour stocker ces éléments. std :: priorité_queue n'est pas un conteneur en soi mais un adoptant de conteneur. Il emballe d'autres conteneurs. Dans cet exemple, nous utilisons un vecteur , mais vous pouvez choisir un autre conteneur prenant en charge les méthodes front(), push_back() et pop_back().
- ' plus grand ' est une fonction de comparaison personnalisée. Cela détermine la manière dont les éléments sont classés dans la file d'attente prioritaire. Dans cet exemple spécifique, Greater met en place un tas min . Cela signifie que le plus petit élément sera en haut de la file d'attente.
Dans le cas du tas maximum, nous n'avons pas eu à les spécifier car leurs valeurs par défaut conviennent déjà au tas maximum.
Exemple:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, plus grand<>int>>>g)> {> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> void> showArray(>int>* arr,>int> n)> {> >for> (>int> i = 0; i cout << arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[6] = { 10, 2, 4, 8, 6, 9 }; priority_queue |
>
>Sortir
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
File d'attente prioritaire minimale du tas
Note: La syntaxe ci-dessus peut être difficile à retenir, donc dans le cas de valeurs numériques, nous pouvons multiplier les valeurs par -1 et utiliser max tas pour obtenir l'effet de tas min. Non seulement nous pouvons utiliser une méthode de tri personnalisée en remplaçant plus grand avec fonction de comparaison personnalisée.
Méthodes de file d'attente prioritaire
La liste suivante de toutes les méthodes de la classe std::priority_queue :
| Méthode | Définition |
|---|---|
| priorité_queue::vide() | Indique si la file d'attente est vide. |
| priorité_queue::size() | Renvoie la taille de la file d'attente. |
| priorité_queue::top() | Renvoie une référence à l'élément le plus haut de la file d'attente. |
| priorité_queue::push() | Ajoute l'élément 'g' à la fin de la file d'attente. |
| priorité_queue::pop() | Supprime le premier élément de la file d'attente. |
| priorité_queue::swap() | Utilisé pour échanger le contenu de deux files d'attente à condition que les files d'attente soient du même type, bien que les tailles puissent différer. |
| priorité_queue::emplace() | Utilisé pour insérer un nouvel élément dans le conteneur de file d'attente prioritaire. |
| type_valeur_file_d'attente_priorité | Représente le type d'objet stocké en tant qu'élément dans une file d'attente prioritaire. Il agit comme synonyme du paramètre de modèle. |
Opérations sur la file d'attente prioritaire en C++
1. Insertion et suppression d'éléments d'une file d'attente prioritaire
Le pousser() La méthode est utilisée pour insérer un élément dans la file d’attente prioritaire. Pour supprimer un élément de la file d'attente prioritaire, le populaire() La méthode est utilisée car elle supprime l’élément ayant la priorité la plus élevée.
Vous trouverez ci-dessous le programme C++ pour diverses fonctions dans la file d'attente prioritaire :
C++
// C++ Program to demonstrate various> // method/function in Priority Queue> #include> #include> using> namespace> std;> // Implementation of priority queue> void> showpq(priority_queue<>int>>gq)> {> >priority_queue<>int>>g = gq;> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> // Driver Code> int> main()> {> >priority_queue<>int>>gquiz;> >// used in inserting the element> >gquiz.push(10);> >gquiz.push(30);> >gquiz.push(20);> >gquiz.push(5);> >gquiz.push(1);> >cout <<>'The priority queue gquiz is : '>;> > >// used for highlighting the element> >showpq(gquiz);> >// used for identifying the size> >// of the priority queue> >cout <<>'
gquiz.size() : '> <<> >gquiz.size();> >// used for telling the top element> >// in priority queue> >cout <<>'
gquiz.top() : '> <<> >gquiz.top();> >// used for popping the element> >// from a priority queue> >cout <<>'
gquiz.pop() : '>;> >gquiz.pop();> >showpq(gquiz);> >return> 0;> }> |
>
>Sortir
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Reportez-vous à la fin pour l'analyse de la complexité.
Note : Ci-dessus, l'une des méthodes d'initialisation de la file d'attente prioritaire. Pour en savoir plus sur l'initialisation efficace de la file d'attente prioritaire, cliquez ici.
2. Pour accéder à l'élément supérieur de la file d'attente prioritaire
L'élément supérieur de la file d'attente prioritaire était accessible à l'aide du haut() méthode.
C++
// C++ program to access the top> // element of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of int> >priority_queue<>int>>chiffres;> >// add items to priority_queue> >numbers.push(1);> >numbers.push(20);> >numbers.push(7);> >// get the element at the top> >cout <<>'Top element: '> <<> >numbers.top();> >return> 0;> }> |
>
>Sortir
Top element: 20>
Reportez-vous à la fin pour l'analyse de la complexité.
10 sur 50,00
Note: Nous ne pouvons accéder qu'à l'élément supérieur de la file d'attente prioritaire.
3. Pour vérifier si la file d'attente prioritaire est vide ou non :
Nous utilisons la méthode empty() pour vérifier si la Priority_queue est vide. Cette méthode renvoie :
- True – Il est renvoyé lorsque la file d'attente prioritaire est vide et est représenté par 1. False – Il est produit lorsque la file d'attente prioritaire n'est pas vide ou False et est caractérisé par 0.
Exemple:
C++
// C++ program to demonstrate> // Implementation of empty() function> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >priority_queue<>int>>pqueueGFG;> >pqueueGFG.push(1);> > >// Priority Queue becomes 1> >// check if it is empty or not> >if> (pqueueGFG.empty())> >{> >cout <<>'Empty or true'>;> >}> >else> >{> >cout <<>'Contains element or False'>;> >}> >return> 0;> }> |
>
>Sortir
Contains element or False>
Reportez-vous à la fin pour l'analyse de la complexité.
4. Pour obtenir/vérifier la taille de la file d'attente prioritaire
Il détermine la taille d'une file d'attente prioritaire. En termes simples, le taille() La méthode est utilisée pour obtenir le nombre d’éléments présents dans le File d'attente de priorité .
Vous trouverez ci-dessous le programme C++ permettant de vérifier la taille de la file d'attente prioritaire :
C++
// C++ program to demonstrate the> // size() method of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of string> >priority_queue pqueue;> >// add items to priority_queue> >pqueue.push(>'Geeks'>);> >pqueue.push(>'for'>);> >pqueue.push(>'Geeks'>);> >pqueue.push(>'C++'>);> >// get the size of queue> >int> size = pqueue.size();> >cout <<>'Size of the queue: '> << size;> >return> 0;> }> |
>
>Sortir
Size of the queue: 4>
Reportez-vous à la fin pour l'analyse de la complexité.
5. Pour échanger le contenu d'une file d'attente prioritaire avec une autre de type similaire
Échanger() La fonction est utilisée pour échanger le contenu d’une file d’attente prioritaire avec une autre file d’attente prioritaire du même type et de taille identique ou différente.
Vous trouverez ci-dessous le programme C++ permettant d'échanger le contenu d'une file d'attente prioritaire avec une autre de type similaire :
C++
// CPP program to illustrate> // Implementation of swap() function> #include> using> namespace> std;> // Print elements of priority queue> void> print(priority_queue<>int>>pq)> {> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >cout << endl;> }> int> main()> {> >// priority_queue container declaration> >priority_queue<>int>>pq1;> >priority_queue<>int>>pq2;> >// pushing elements into the 1st priority queue> >pq1.push(1);> >pq1.push(2);> >pq1.push(3);> >pq1.push(4);> >// pushing elements into the 2nd priority queue> >pq2.push(3);> >pq2.push(5);> >pq2.push(7);> >pq2.push(9);> >cout <<>'Before swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >// using swap() function to swap elements of priority> >// queues> >pq1.swap(pq2);> >cout << endl <<>'After swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Sortir
Before swapping:- Priority Queue 1 = 4 3 2 1 Priority Queue 2 = 9 7 5 3 After swapping:- Priority Queue 1 = 9 7 5 3 Priority Queue 2 = 4 3 2 1>
Reportez-vous à la fin pour l'analyse de la complexité.
6. Pour insérer un nouvel élément dans le conteneur de file d'attente prioritaire
Placer() La fonction est utilisée pour insérer un nouvel élément dans le conteneur de file d'attente prioritaire, le nouvel élément est ajouté à la file d'attente prioritaire en fonction de sa priorité. C'est similaire à l'opération de poussée. La différence est que l'opération emplace() enregistre une copie inutile de l'objet.
Vous trouverez ci-dessous le programme C++ permettant d'insérer un nouvel élément dans le conteneur de file d'attente prioritaire :
C++
// CPP program to illustrate> // Implementation of emplace() function> #include> using> namespace> std;> int> main()> {> >priority_queue<>int>>pq;> >pq.emplace(1);> >pq.emplace(2);> >pq.emplace(3);> >pq.emplace(4);> >pq.emplace(5);> >pq.emplace(6);> >// Priority queue becomes 1, 2, 3, 4, 5, 6> >// Printing the priority queue> >cout <<>'Priority Queue = '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Sortir
Priority Queue = 6 5 4 3 2 1>
Reportez-vous à la fin pour l'analyse de la complexité.
7. Pour représenter le type d'objet stocké en tant qu'élément dans une file d'attente prioritaire
La méthode Priority_queue :: value_type est une fonction intégrée en C++ STL qui représente le type d'objet stocké en tant qu'élément dans une Priority_queue. Il agit comme synonyme du paramètre de modèle.
Syntaxe:
priority_queue::value_type variable_name>
Vous trouverez ci-dessous le programme C++ pour représenter le type d'objet stocké en tant qu'élément dans une file d'attente prioritaire :
C++
// C++ program to illustrate the> // priority_queue :: value_type function> #include> using> namespace> std;> // Driver code> int> main()> {> >// declare integer value_type for priority queue> >priority_queue<>int>>::value_type AnInt;> >// declare string value_type for priority queue> >priority_queue::value_type AString;> >// Declares priority_queues> >priority_queue<>int>>q1;> >priority_queue q2;> >// Here AnInt acts as a variable of int data type> >AnInt = 20;> >cout <<>'The value_type is AnInt = '> << AnInt << endl;> >q1.push(AnInt);> >AnInt = 30;> >q1.push(AnInt);> >cout <<>'Top element of the integer priority_queue is: '> ><< q1.top() << endl;> >// here AString acts as a variable of string data type> >AString =>'geek'>;> >cout << endl> ><<>'The value_type is AString = '> << AString> ><< endl;> >q2.push(AString);> >AString =>'for'>;> >q2.push(AString);> >AString =>'geeks'>;> >q2.push(AString);> >cout <<>'Top element of the string priority_queue is: '> ><< q2.top() << endl;> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Sortir
The value_type is AnInt = 20 Top element of the integer priority_queue is: 30 The value_type is AString = geek Top element of the string priority_queue is: geeks>
Reportez-vous à la fin pour l'analyse de la complexité.
Complexités de toutes les opérations :
| Méthodes tostring java | Complexité temporelle | Espace auxiliaire |
|---|---|---|
| priorité_queue::vide() | O(1) | O(1) |
| priorité_queue::size() | O(1) | O(1) |
| priorité_queue::top() | O(1) | O(1) |
| priorité_queue::push() | O (logN) | O(1) |
| priorité_queue::pop() | O (logN) | O(1) |
| priorité_queue::swap() | O(1) | SUR) |
| priorité_queue::emplace() | O (logN) | O(1) |
| type_valeur_file_d'attente_priorité | O(1) | O(1) |