Comment utiliser C++ Priority_queue?

En C++, une file d'attente est une structure de données de liste où le premier élément à mettre dans la liste est le premier élément à supprimer, lorsque la suppression doit avoir lieu. Une file d'attente prioritaire en C++ est similaire, mais a un certain ordre ; c'est l'élément de plus grande valeur qui est supprimé en premier. La file d'attente prioritaire peut toujours être configurée pour que ce soit l'élément ayant le moins de valeur qui soit supprimé en premier. Toute file d'attente doit avoir au moins le pousser() fonction et le pop() une fonction. le pousser() la fonction ajoute un nouvel élément à l'arrière. Pour la file d'attente normale, le pop() la fonction supprime le premier élément jamais inséré. Pour la file d'attente prioritaire, le pop() la fonction supprime l'élément avec la priorité la plus élevée, qui peut être la plus grande ou la plus petite, selon le schéma de commande.

Afin d'utiliser la priorité_queue C++, le programme doit commencer par un code tel que :

#inclure
#inclure
en utilisant l'espace de noms std ;

Il inclut la bibliothèque de files d'attente dans le programme.

Afin de continuer à lire, le lecteur doit avoir une connaissance de base de C++.

Contenu de l'article

Introduction - voir ci-dessus
Construction de base
Fonctions membres importantes
Autres fonctions de file d'attente prioritaire
Données de chaîne
Autres constructions de file d'attente prioritaires
Conclusion

Construction de base

La structure de données doit être construite avant de pouvoir être utilisée. La construction signifie ici instancier un objet de la classe de file d'attente de la bibliothèque. L'objet file d'attente doit alors avoir un nom qui lui est donné par le programmeur. La syntaxe la plus simple pour créer une file d'attente prioritaire est :

File d'attente de priorité nom de file d'attente ;

Avec cette syntaxe, la plus grande valeur est supprimée en premier. Un exemple d'instanciation est :

File d'attente de priorité pq;

ou alors

File d'attente de priorité pq;

Le vecteur et le deque sont deux structures de données en C++. Une priorité_queue peut être créée avec l'un ou l'autre. La syntaxe pour créer une file d'attente prioritaire à partir de la structure vectorielle est :

File d'attente de priorité, comparer> pq;

Un exemple de cette instanciation est :

File d'attente de priorité, moins > pq;

Notez l'écart entre > et > à la fin de la déclaration. Ceci afin d'éviter toute confusion avec >>. Le code de comparaison par défaut est « moins”, ce qui signifie la plus grande, et pas nécessairement la première valeur, serait supprimée en premier. Ainsi, la déclaration de création peut simplement être écrite comme:

File d'attente de priorité > pq;

Si la plus petite valeur doit être supprimée en premier, alors l'instruction doit être :

File d'attente de priorité, plus grand > pq;

Fonctions membres importantes

La fonction push()
Cette fonction pousse une valeur, qui est son argument, dans la priorité_queue. Il renvoie le vide. Le code suivant illustre cela :

File d'attente de priorité pq;
pq.pousser(10) ;
pq.pousser(30);
pq.pousser(20);
pq.pousser (50);
pq.pousser (40);

Cette priorité_queue a reçu 5 valeurs entières de l'ordre de 10, 30, 20, 50, 40. Si tous ces éléments doivent être retirés de la file d'attente prioritaire, ils sortiront dans l'ordre de 50, 40, 30, 20, 10.

La fonction pop()
Cette fonction supprime de la priorité_queue la valeur avec la priorité la plus élevée. Si le code de comparaison est « plus”, alors il supprimera l'élément avec la plus petite valeur. S'il est appelé à nouveau, il supprime l'élément suivant avec la plus petite valeur du reste ; appelé à nouveau, il supprime la prochaine plus petite valeur présente, et ainsi de suite. Il renvoie le vide. Le code suivant illustre cela :

File d'attente de priorité, plus grand > pq;
pq.pousser('a'); pq.pousser('c'); pq.pousser('b'); pq.pousser('e'); pq.push('d');

Notez que pour appeler une fonction membre, le nom de l'objet doit être suivi d'un point, puis la fonction.

La fonction top()
le pop() La fonction supprime la valeur suivante de la priorité la plus élevée, mais ne la renvoie pas, car pop() est une fonction vide. Utilisez le Haut() fonction afin de connaître la valeur de priorité la plus élevée qui doit être supprimée ensuite. le Haut() la fonction renvoie une copie de la valeur de priorité la plus élevée dans la file d'attente prioritaire. Le code suivant, où la valeur suivante de la priorité la plus élevée est la valeur la moins élevée, illustre cette

File d'attente de priorité, plus grand > pq;
pq.pousser('a'); pq.pousser('c'); pq.pousser('b'); pq.pousser('e'); pq.push('d');
car ch1 = pq.Haut(); pq.pop();
car ch2 = pq.Haut(); pq.pop();
car ch3 = pq.Haut(); pq.pop();
car ch4 = pq.Haut(); pq.pop();
car ch5 = pq.Haut(); pq.pop();
cout<La sortie est "a"b"c"d"e'.

La fonction vide()
Si un programmeur utilise le Haut() fonction sur une file d'attente_priorité vide, après la compilation réussie, il recevrait un message d'erreur tel que :

Segmentation fault (core dumped)

Donc, vérifiez toujours si la file d'attente prioritaire n'est pas vide avant d'utiliser le Haut() une fonction. le vider() la fonction membre renvoie un bool, true si la file d'attente est vide et false si la file d'attente n'est pas vide. Le code suivant illustre cela :

File d'attente de priorité pq;
entier i1 = 10; entier i2 = 30 ; entier i3 = 20; entier i4 = 50 ; entier i5 = 40 ;
pq.pousser(i1) ; pq.pousser(i2) ; pq.pousser(i3) ; pq.pousser(i4) ; pq.pousser(i5) ;
tandis que(!pq.vider())

cout << pq.top() << ";
pq.pop();

cout << '\n';

Autres fonctions de file d'attente prioritaire

La fonction size()
Cette fonction renvoie la longueur de la file d'attente prioritaire, comme l'illustre le code suivant :

La sortie est de 5.

La fonction swap()
Si deux priority_queues sont du même type et de la même taille, elles peuvent être échangées par cette fonction, comme le montre le code suivant :

File d'attente de priorité pq1 ;
entier i1 = 10; entier i2 = 30 ; entier i3 = 20; entier i4 = 50 ; entier i5 = 40 ;
pq1.pousser(i1) ; pq1.pousser(i2) ; pq1.pousser(i3) ; pq1.pousser(i4) ; pq1.pousser(i5) ;
File d'attente de priorité pqA;
int it1 = 1; int it2 = 3; int it3 = 2; int it4 = 5; int it5 = 4;
pqA.pousser(it1) ; pqA.pousser(it2) ; pqA.pousser(it3) ; pqA.pousser(it4) ; pqA.pousser(it5) ;
pq1.échanger(pqA);
tandis que(!pq1.vider())

cout << pq1.top() << ";
pq1.pop();
cout<<'\n';
tandis que(!pqA.vider())

cout << pqA.top() << ";
pqA.pop();
cout<<'\n';

La sortie est :

5 4 3 2 1
50 40 30 20 10

La fonction emplace()
le remplacer() la fonction est similaire à la fonction push. Le code suivant illustre cela :

File d'attente de priorité pq1 ;
entier i1 = 10; entier i2 = 30 ; entier i3 = 20; entier i4 = 50 ; entier i5 = 40 ;
pq1.remplacer(i1) ; pq1.mettre en place(i2) ; pq1.mettre en place(i3) ; pq1.mettre en place (i4) ; pq1.mettre en place(i5) ;
tandis que(!pq1.vider())

cout << pq1.top() << ";
pq1.pop();
cout<<'\n';

La sortie est :

50 40 30 20 10

Données de chaîne

Lors de la comparaison de chaînes, la classe de chaîne doit être utilisée et non l'utilisation directe des littéraux de chaîne car elle comparerait les pointeurs et non les chaînes réelles. Le code suivant montre comment la classe de chaîne est utilisée :

#inclure
File d'attente de priorité pq1 ;
chaîne s1 = chaîne("stylo"), s2 = chaîne("crayon"), s3 = chaîne("livre d'exercices"), s4 = chaîne("livre de texte"), s5 = chaîne("règle");
pq1.pousser(s1) ; pq1.pousser(s2) ; pq1.pousser(s3) ; pq1.pousser(s4) ; pq1.pousser(s5) ;
tandis que(!pq1.vider())

cout << pq1.top() << " ";
pq1.pop();
cout<<'\n';

La sortie est :

livre de texte règle crayon stylo cahier d'exercices

Autres constructions de file d'attente prioritaires

Création explicite à partir d'un vecteur
Une file d'attente prioritaire peut être créée explicitement à partir d'un vecteur comme le montre le code suivant :

#inclure
vecteur vtr = 10, 30, 20, 50, 40 ;
File d'attente de priorité pq(vtr.commencer(), vtr.finir());
tandis que(!pq.vider())

cout << pq.top() << ";
pq.pop();
cout<<'\n';

La sortie est : 50 40 30 20 10. Cette fois, l'en-tête du vecteur doit également être inclus. Les arguments de la fonction constructeur prennent les pointeurs de début et de fin du vecteur. Le type de données pour le vecteur et le type de données pour le priority_queue doivent être les mêmes.

Afin de faire de la moindre valeur la priorité, la déclaration pour le constructeur serait :

File d'attente de priorité, plus grand>int> > pq(vtr.commencer(), vtr.finir());

Création explicite à partir d'un tableau
Une file d'attente prioritaire peut être créée explicitement à partir d'un tableau comme le montre le code suivant :

int arr[] = 10, 30, 20, 50, 40 ;
File d'attente de priorité pq(arr, arr+5) ;
tandis que(!pq.vider())

cout << pq.top() << ";
pq.pop();
cout<<'\n';

La sortie est : 50 40 30 20 10. Les arguments de la fonction constructeur prennent les pointeurs de début et de fin du tableau. arr renvoie le pointeur de départ, « arr+5 » renvoie le pointeur juste après le tableau et 5 est la taille du tableau. Le type de données pour le tableau et le type de données pour le priority_queue doivent être les mêmes.

Afin de faire de la moindre valeur la priorité, la déclaration pour le constructeur serait :

File d'attente de priorité, plus grand > pq(arr, arr+5) ;

Remarque : en C++, la priorité_queue est en fait appelée un adaptateur, pas seulement un conteneur.

Code de comparaison personnalisé

Avoir toutes les valeurs dans la file d'attente prioritaire ascendante ou descendante n'est pas la seule option pour la file d'attente prioritaire. Par exemple, une liste de 11 entiers pour un tas maximum est :

88, 86, 87, 84, 82, 79,74, 80, 81, , , 64, 69

La valeur la plus élevée est 88. Ceci est suivi de deux nombres : 86 et 87, qui sont inférieurs à 88. Le reste des nombres est inférieur à ces trois nombres, mais pas vraiment dans l'ordre. Il y a deux cellules vides dans la liste. Les nombres 84 et 82 sont inférieurs à 86. Les nombres 79 et 74 sont inférieurs à 87. Les nombres 80 et 81 sont inférieurs à 84. Les nombres 64 et 69 sont inférieurs à 79.

Le placement des nombres suit les critères max-heap - voir plus loin. Afin de fournir un tel schéma pour la priorité_queue, le programmeur doit fournir son propre code de comparaison - voir plus loin.

Conclusion

Une priorité_queue C++ est une file d'attente premier entré, premier sorti. La fonction membre, pousser(), ajoute une nouvelle valeur dans la file d'attente. La fonction membre, Haut(), lit la valeur supérieure dans la file d'attente. La fonction membre, pop(), supprime sans retourner la valeur supérieure de la file d'attente. La fonction membre, vider(), vérifie si la file d'attente est vide. Cependant, la priorité_queue diffère de la file d'attente, en ce sens qu'elle suit un algorithme de priorité. Il peut être le plus grand, du premier au dernier, ou le moins, du premier au dernier. Les critères (algorithme) peuvent également être définis par le programmeur.