Tas et file d'attente prioritaire en C++

Le tas et la file d'attente prioritaire sont des structures de données couramment utilisées en C++, et elles ont toutes deux une valeur d'application importante. Cet article présentera et analysera respectivement le tas et la file d'attente prioritaire pour aider les lecteurs à mieux les comprendre et les utiliser.

1. Heap

Le tas est une structure de données arborescente spéciale qui peut être utilisée pour implémenter des files d'attente prioritaires. Dans le tas, chaque nœud satisfait les propriétés suivantes :

1. Sa valeur n'est pas inférieure (ou pas supérieure) à la valeur de son nœud parent.
2. Ses sous-arbres gauche et droit forment également un tas.

Nous appelons un tas qui n'est pas plus petit que son nœud parent un « tas min » et un tas qui n'est pas plus grand que son nœud parent un « tas max ». De plus, le tas est généralement un arbre binaire complet, c'est-à-dire que les nœuds des autres niveaux sont pleins, à l'exception du dernier niveau, où les nœuds sont disposés de gauche à droite.

En C++, la bibliothèque STL fournit deux classes, heap et priorité_queue, pour implémenter le tas. Parmi elles, la classe tas fournit des fonctions d'opération de tas, telles que make_heap, push_heap, pop_heap, etc., et la classe priorité_queue est une file d'attente prioritaire basée sur l'implémentation du tas. Examinons ensuite l'utilisation de tas et de priorité_queue.

1. classe de tas

(1) Créer un tas

Avant de créer un tas, vous devez créer un tableau de type vectoriel pour stocker les nombres à trier :

vecteur 4, 1, 5, 9, 2, 6, 5, 3 };

Ensuite, nous pouvons utiliser la fonction make_heap pour convertir le tableau de type vectoriel en tas :

make_heap(v.begin(), v.end (), Greater());

Parmi eux, Greater() représente une fonction de comparaison qui peut contrôler le type de tas.

(2) Insérer des éléments

Pour insérer des éléments dans le tas, vous pouvez utiliser la fonction push_heap Son utilisation est la suivante :

v.push_back(7);
push_heap(v.begin(), v.end. (), Greater());

(3) Supprimer des éléments

Pour supprimer des éléments du tas, vous pouvez utiliser la fonction pop_heap, qui déplacera l'élément supérieur du tas vers la dernière position du tas. et supprimez l'élément du tas. L'utilisation de cette fonction est la suivante :

pop_heap(v.begin(), v.end(), Greater());
v.pop_back();

2. priority_queue class

(1 ) Créer un tas

Contrairement à la classe heap, la classe priorité_queue peut spécifier le type de tas lors de la déclaration de l'objet, comme suit :

priority_queue, Greater> signifie créer un tas minimum .

(2) Insérer des éléments

L'insertion d'éléments dans priorité_queue peut utiliser directement la fonction push, comme indiqué ci-dessous :

q.push(2);

q.push(4); q.push(9);

(3) Supprimer des éléments

Pour supprimer des éléments dans priorité_queue, vous pouvez directement utiliser la fonction pop, comme indiqué ci-dessous :

q.pop();

2. La file d'attente prioritaire est une file d'attente spéciale qui trie les éléments en fonction de leur priorité, en plaçant les éléments ayant la priorité la plus élevée en début de file d'attente et les éléments ayant la priorité la plus basse à la fin de la file d'attente. Vous pouvez utiliser un tas pour implémenter une file d'attente prioritaire.

En C++, la classe priorité_queue est une file d'attente prioritaire implémentée basée sur le tas. Elle peut utiliser les fonctions des classes de tas et de priorité_queue ci-dessus pour effectuer des opérations d'insertion et de suppression d'éléments. De plus, la fonction top est également fournie dans la classe priorité_queue, qui est utilisée pour accéder à l'élément ayant la priorité la plus élevée, comme indiqué ci-dessous :

priority_queue q;

q.push(2);

q.push (4);

q .push(1);

q.push(9);

cout
Résumé :

Cet article présente le tas et la priorité dans la file d'attente C++, et analysé les principes d'utilisation et de mise en œuvre du tas et de la file d'attente prioritaire respectivement. En étudiant cet article, les lecteurs peuvent mieux comprendre ces deux structures de données et les utiliser de manière flexible dans la programmation réelle. Dans le même temps, les lecteurs doivent prêter attention au timing et aux précautions d'utilisation du tas et de la file d'attente prioritaire afin de garantir l'exactitude et l'efficacité du code.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!