FILE D'ATTENTE PRIORITAIRE (STRUCTURES DE DONNÉES)

Une file d'attente prioritaire est un type de données abstrait qui se comporte de manière similaire à la file d'attente normale, sauf que chaque élément a une certaine priorité, c'est-à-dire que l'élément ayant la priorité la plus élevée viendrait en premier dans une file d'attente prioritaire. La priorité des éléments dans une file d'attente prioritaire déterminera l'ordre dans lequel les éléments sont supprimés de la file d'attente prioritaire.

La file d'attente prioritaire ne prend en charge que les éléments comparables, ce qui signifie que les éléments sont classés par ordre croissant ou décroissant.

comparer la chaîne java

Par exemple, supposons que nous ayons des valeurs telles que 1, 3, 4, 8, 14, 22 insérées dans une file d'attente prioritaire avec un ordre imposé aux valeurs allant du plus petit au plus grand. Par conséquent, le numéro 1 aurait la priorité la plus élevée tandis que le numéro 22 aurait la priorité la plus basse.

Caractéristiques d'une file d'attente prioritaire

Une file d'attente prioritaire est une extension d'une file d'attente qui contient les caractéristiques suivantes :

Chaque élément d'une file d'attente prioritaire est associé à une priorité.
Un élément avec la priorité la plus élevée sera supprimé avant la suppression de la priorité la moindre.
Si deux éléments d'une file d'attente prioritaire ont la même priorité, ils seront disposés selon le principe FIFO.

Comprenons la file d'attente prioritaire à travers un exemple.

Nous avons une file d'attente prioritaire qui contient les valeurs suivantes :

1, 3, 4, 8, 14, 22

Toutes les valeurs sont classées par ordre croissant. Maintenant, nous allons observer à quoi ressemblera la file d'attente prioritaire après avoir effectué les opérations suivantes :

sondage():Cette fonction supprimera l'élément la plus prioritaire de la file d'attente prioritaire. Dans la file d'attente prioritaire ci-dessus, l'élément « 1 » a la priorité la plus élevée, il sera donc supprimé de la file d'attente prioritaire.ajouter(2):Cette fonction insérera l'élément '2' dans une file d'attente prioritaire. Comme 2 est le plus petit élément parmi tous les nombres, il obtiendra la priorité la plus élevée.sondage():Cela supprimera l'élément « 2 » de la file d'attente prioritaire car il a la file d'attente la plus prioritaire.ajouter(5):Il insérera 5 éléments après 4 car 5 est supérieur à 4 et inférieur à 8, il obtiendra donc la troisième priorité la plus élevée dans une file d'attente prioritaire.

Types de file d'attente prioritaire

Il existe deux types de file d'attente prioritaire :

Représentation de la file d'attente prioritaire

Nous allons maintenant voir comment représenter la file d'attente prioritaire à travers une liste à sens unique.

Nous allons créer la file d'attente prioritaire en utilisant la liste ci-dessous dans laquelle INFO la liste contient les éléments de données, PNR La liste contient les numéros de priorité de chaque élément de données disponible dans la INFO liste, et LINK contient essentiellement l’adresse du nœud suivant.

Créons la file d'attente prioritaire étape par étape.

applications cachées sur cet appareil

Dans le cas d'une file d'attente prioritaire, le numéro de priorité inférieure est considéré comme la priorité la plus élevée, c'est-à-dire : numéro de priorité inférieure = priorité plus élevée.

Étape 1: Dans la liste, le numéro de priorité inférieure est 1, dont la valeur des données est 333, il sera donc inséré dans la liste comme indiqué dans le diagramme ci-dessous :

Étape 2: Après avoir inséré 333, la priorité numéro 2 a une priorité plus élevée et les valeurs de données associées à cette priorité sont 222 et 111. Ainsi, ces données seront insérées sur la base du principe FIFO ; donc 222 seront ajoutés en premier, puis 111.

Étape 3: Après avoir inséré les éléments de priorité 2, le numéro de priorité immédiatement supérieur est 4 et les éléments de données associés à 4 numéros de priorité sont 444, 555, 777. Dans ce cas, les éléments seraient insérés selon le principe FIFO ; par conséquent, 444 seront ajoutés en premier, puis 555 et enfin 777.

Étape 4: Après avoir inséré les éléments de priorité 4, le numéro de priorité immédiatement supérieur est 5, et la valeur associée à la priorité 5 est 666, il sera donc inséré à la fin de la file d'attente.

Mise en œuvre de la file d'attente prioritaire

La file d'attente prioritaire peut être implémentée de quatre manières : tableaux, liste chaînée, structure de données en tas et arbre de recherche binaire. La structure de données de tas est le moyen le plus efficace d'implémenter la file d'attente prioritaire, nous allons donc implémenter la file d'attente prioritaire à l'aide d'une structure de données de tas dans cette rubrique. Maintenant, commençons par comprendre la raison pour laquelle le tas est le moyen le plus efficace parmi toutes les autres structures de données.

Analyse des complexités à l'aide de différentes implémentations

Mise en œuvre	ajouter	Retirer	coup d'oeil
Liste chaînée	O(1)	Sur)	Sur)
Tas binaire	O (connexion)	O (connexion)	O(1)
Arbre de recherche binaire	O (connexion)	O (connexion)	O(1)

Qu’est-ce que le tas ?

Un tas est une structure de données arborescente qui forme un arbre binaire complet et satisfait à la propriété du tas. Si A est un nœud parent de B, alors A est ordonné par rapport au nœud B pour tous les nœuds A et B d'un tas. Cela signifie que la valeur du nœud parent peut être supérieure ou égale à la valeur du nœud enfant, ou que la valeur du nœud parent peut être inférieure ou égale à la valeur du nœud enfant. On peut donc dire qu’il existe deux types de tas :

Les deux tas sont le tas binaire, car chacun a exactement deux nœuds enfants.

Opérations de file d'attente prioritaire

Les opérations courantes que nous pouvons effectuer sur une file d'attente prioritaire sont l'insertion, la suppression et le coup d'œil. Voyons comment nous pouvons maintenir la structure des données du tas.

Insertion de l'élément dans une file d'attente prioritaire (tas max)

Si nous insérons un élément dans une file d'attente prioritaire, il se déplacera vers l'emplacement vide en regardant de haut en bas et de gauche à droite.

Si l'élément n'est pas au bon endroit alors il est comparé au nœud parent ; s'il s'avère en panne, les éléments sont échangés. Ce processus se poursuit jusqu'à ce que l'élément soit placé dans une position correcte.

Suppression de l'élément minimum de la file d'attente prioritaire

Comme nous le savons, dans un tas max, l'élément maximum est le nœud racine. Lorsque nous supprimons le nœud racine, cela crée un emplacement vide. Le dernier élément inséré sera ajouté dans cet emplacement vide. Ensuite, cet élément est comparé aux nœuds enfants, c'est-à-dire l'enfant gauche et l'enfant droit, et échangé avec le plus petit des deux. Il continue de descendre dans l'arborescence jusqu'à ce que la propriété du tas soit restaurée.

Applications de la file d'attente prioritaire

Voici les applications de la file d'attente prioritaire :

index de Java

Il est utilisé dans l'algorithme du chemin le plus court de Dijkstra.
Il est utilisé dans l'algorithme de prim
Il est utilisé dans les techniques de compression de données comme le code Huffman.
Il est utilisé sous forme de tas.
Il est également utilisé dans les systèmes d'exploitation comme la planification des priorités, l'équilibrage de charge et la gestion des interruptions.

Programme pour créer la file d'attente prioritaire en utilisant le tas binaire max.

 #include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i &gt; 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong>  </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>

TechCodeview

Qu'est-ce qu'une file d'attente prioritaire ?