File d'attente prioritaire dans la structure de données : caractéristiques, types et implémentation

Publié: 2021-05-02

Table des matières

introduction

La file d'attente prioritaire dans la structure de données est une extension de la file d'attente "normale". C'est un type de données abstrait qui contient un groupe d'éléments. C'est comme la file d'attente "normale" sauf que les éléments de sortie de file suivent un ordre de priorité. L'ordre de priorité retire d'abord les éléments qui ont la priorité la plus élevée. Ce blog vous permettra de mieux comprendre la file d'attente prioritaire et son implémentation dans le langage de programmation C.

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

C'est un type de données abstrait qui fournit un moyen de maintenir l'ensemble de données. La file d'attente « normale » suit un modèle de premier entré, premier sorti. Il retire les éléments de la file d'attente dans le même ordre suivi au moment de l'opération d'insertion. Cependant, l'ordre des éléments dans une file d'attente prioritaire dépend de la priorité de l'élément dans cette file d'attente. La file d'attente prioritaire déplace les éléments de priorité la plus élevée au début de la file d'attente prioritaire et les éléments de priorité la plus faible à l'arrière de la file d'attente prioritaire.

Il ne prend en charge que les éléments comparables. Par conséquent, une file d'attente prioritaire dans la structure de données organise les éléments dans l'ordre croissant ou décroissant.

Vous pouvez imaginer une file d'attente prioritaire comme plusieurs patients faisant la queue dans un hôpital. Ici, la situation du patient définit l'ordre de priorité. Le patient avec la blessure la plus grave serait le premier dans la file d'attente.

Quelles sont les caractéristiques d'une file d'attente prioritaire ?

Une file d'attente est qualifiée de file d'attente prioritaire si elle présente les caractéristiques suivantes :

  • Chaque élément est associé à une priorité.
  • Un élément avec la priorité la plus élevée est déplacé au premier plan et supprimé en premier.
  • Si deux éléments partagent la même valeur de priorité, la file d'attente prioritaire suit le principe du premier entré, premier sorti pour le fonctionnement de la file d'attente.

Quels sont les types de file d'attente prioritaire ?

Une file d'attente prioritaire est de deux types :

  • File d'attente de priorité de commande croissante
  • File d'attente prioritaire par ordre décroissant

File d'attente de priorité de commande croissante

Une file d'attente de priorité d'ordre croissant donne la priorité la plus élevée au nombre inférieur dans cette file d'attente. Par exemple, vous avez six numéros dans la file d'attente prioritaire qui sont 4, 8, 12, 45, 35, 20. Tout d'abord, vous organiserez ces numéros par ordre croissant. La nouvelle liste est la suivante : 4, 8, 12, 20. 35, 45. Dans cette liste, 4 est le plus petit nombre. Par conséquent, la file d'attente de priorité d'ordre croissant traite le numéro 4 comme la priorité la plus élevée.

4 8 12 20 35 45

Dans le tableau ci-dessus, 4 a la priorité la plus élevée et 45 a la priorité la plus basse.

File d'attente prioritaire par ordre décroissant

Une file d'attente prioritaire par ordre décroissant donne la priorité la plus élevée au numéro le plus élevé dans cette file d'attente. Par exemple, vous avez six numéros dans la file d'attente prioritaire qui sont 4, 8, 12, 45, 35, 20. Tout d'abord, vous organiserez ces numéros par ordre croissant. La nouvelle liste est la suivante : 45, 35, 20, 12, 8, 4. Dans cette liste, 45 est le nombre le plus élevé. Par conséquent, la file d'attente prioritaire par ordre décroissant traite le numéro 45 comme la priorité la plus élevée.

45 35 20 12 8 4

Dans le tableau ci-dessus, 4 a la priorité la plus basse et 45 a la priorité la plus élevée.

Implémentation de la file d'attente prioritaire dans la structure de données

Vous pouvez implémenter les files d'attente prioritaires de l'une des manières suivantes :

  • Liste liée
  • Tas binaire
  • Tableaux
  • Arbre de recherche binaire

Le tas binaire est la méthode la plus efficace pour implémenter la file d'attente prioritaire dans la structure de données .

Les tableaux ci-dessous résument la complexité des différentes opérations dans une file d'attente prioritaire.

Opération Tableau non ordonné Tableau ordonné Tas binaire Arbre de recherche binaire
Insérer 0(1) 0(N) 0(log(N)) 0(log(N))
Coup d'oeil 0(N) 0(1) 0(1) 0(1)
Supprimer 0(N) 0(1) 0(log (N)) 0(log(N))

Tas binaire

Un arbre de tas binaire organise tous les nœuds parents et enfants de l'arbre dans un ordre particulier. Dans un arbre de tas binaire, un nœud parent peut avoir un maximum de 2 nœuds enfants. La valeur du nœud parent peut être :

  • égale ou inférieure à la valeur d'un nœud enfant.
  • égale ou supérieure à la valeur d'un nœud enfant.

Le processus ci-dessus divise le tas binaire en deux types : tas max et tas min.

Tas maximum

Le tas max est un tas binaire dans lequel un nœud parent a une valeur égale ou supérieure à la valeur du nœud enfant. Le nœud racine de l'arbre a la valeur la plus élevée.

Insertion d'un élément dans un arbre binaire Max Heap

Vous pouvez effectuer les étapes suivantes pour insérer un élément/numéro dans la file d'attente prioritaire dans la structure de données .

  1. L'algorithme parcourt l'arbre de haut en bas et de gauche à droite pour trouver un emplacement vide. Il insère ensuite l'élément au dernier nœud de l'arbre.
  2. Après insertion de l'élément, l'ordre de l'arbre binaire est perturbé. Vous devez échanger les données les unes avec les autres pour trier l'ordre de l'arborescence binaire max heap. Vous devez continuer à mélanger les données jusqu'à ce que l'arborescence satisfasse la propriété max-heap.

Algorithme pour insérer un élément dans un arbre binaire Max Heap

Si l'arbre est vide et ne contient aucun noeud,

créer un nouveau nœud parent newElement.

else (un nœud parent est déjà disponible)

insérez le newElement à la fin de l'arbre (c'est-à-dire le dernier nœud de l'arbre de gauche à droite.)

max-heapify l'arbre

Suppression d'un élément dans un arbre binaire Max Heap

  1. Vous pouvez effectuer les étapes suivantes pour supprimer un élément de la file d'attente prioritaire dans la structure de données .
  2. Choisissez l'élément que vous souhaitez supprimer de l'arbre binaire.
  3. Décalez les données à la fin de l'arborescence en les échangeant avec les données du dernier nœud.
  4. Supprimez le dernier élément de l'arbre binaire.
  5. Après suppression de l'élément, l'ordre de l'arbre binaire est perturbé. Vous devez trier l'ordre pour satisfaire la propriété de max-heap. Vous devez continuer à mélanger les données jusqu'à ce que l'arborescence rencontre la propriété max-heap.

Algorithme pour supprimer un élément dans un arbre binaire Max Heap

Si l'élémentUpForDeletion est le dernierNode,

supprimer l'élémentUpForDeletion

sinon remplacer elementUpForDeletion par le lastNode

supprimer l'élémentUpForDeletion

max-heapify l'arbre

Trouver l'élément maximum ou minimum dans un arbre binaire Max Heap

Dans un arbre binaire max heap, l'opération de recherche renvoie le nœud parent (l'élément le plus élevé) de l'arbre.

Algorithme pour trouver le maximum ou le minimum dans un arbre binaire Max Heap

retourner ParentNode

Mise en œuvre du programme de la file d'attente prioritaire à l'aide de l'arborescence binaire Max Heap

#include <stdio.h>

int arbre_binaire = 10 ;

entier tas_max = 0 ;

test int const = 100000 ;

void swap( int *x, int *y ) {

int un ;

un = *x ;

*x= *y ;

*y = un ;

}

//Code pour trouver le parent dans l'arborescence max heap

int findParentNode(int node[], int root) {

if ((racine > 1) && (racine < arbre_binaire)) {

renvoie racine/2 ;

}

retour -1 ;

}

void max_heapify(int node[], int root) {

int leftNodeRoot = findLeftChild(nœud, racine);

int rightNodeRoot = findRightChild(nœud, racine);

// trouver le plus élevé parmi la racine, l'enfant gauche et l'enfant droit

int le plus élevé = racine ;

si ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

if (node[leftNodeRoot] > node[highest]) {

le plus élevé = leftNodeRoot ;

}

}

si ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

if (node[rightNodeRoot] > node[highest]) {

le plus élevé = rightNodeRoot ;

}

}

si (le plus élevé != racine) {

swap(&nœud[racine], &nœud[le plus élevé]);

max_heapify(nœud, le plus haut);

}

}

void create_max_heap(int node[]) {

entier d ;

for(d=max_heap/2; d>=1; d–) {

max_heapify(nœud, d);

}

}

int maximum(int nœud[]) {

nœud de retour[1] ;

}

int find_max(int ​​nœud[]) {

int maxNode = nœud[1] ;

nœud[1] = nœud[max_heap] ;

tas_max– ;

max_heapify(noeud, 1);

renvoie maxNode ;

}

void descend_key(int node[], int node, int key) {

A[racine] = clé ;

max_heapify(nœud, racine);

}

void augment_key(int node[], int root, int key) {

nœud[racine] = clé ;

tandis que((racine>1) && (nœud[trouverNoeudParent(nœud, racine)] < nœud[racine])) {

swap(&node[racine], &node[findParentNode(noeud, racine)]);

racine = findParentNode(nœud, racine);

}

}

void insert(int node[], int key) {

tas_max++ ;

nœud[max_heap] = -1*test ;

augmentation_clé(noeud, max_heap, clé);

}

void display_heap(int node[]) {

entier d ;

for(d=1; d<=max_heap; d++) {

printf("%d\n",noeud[d]);

}

printf("\n");

}

int main() {

int node[binary_tree] ;

insérer(noeud, 10);

insérer(noeud, 4);

insérer(noeud, 20);

insérer(noeud, 50);

insérer(noeud, 1);

insérer(noeud, 15);

display_heap(nœud);

printf("%d\n\n", maximum(noeud));

display_heap(nœud);

printf("%d\n", extract_max(noeud));

printf("%d\n", extract_max(noeud));

renvoie 0 ;

}

Tas minimal

Le tas min est un tas binaire dans lequel un nœud parent a une valeur égale ou inférieure à la valeur du nœud enfant. Le nœud racine de l'arbre a la valeur la plus faible.

Vous pouvez implémenter le min-heap de la même manière que le max-heap, sauf que l'ordre est inversé.

Conclusion

Les exemples donnés dans l'article sont uniquement à des fins explicatives. Vous pouvez modifier les déclarations ci-dessus selon vos besoins. Dans ce blog, nous avons découvert le concept de file d'attente prioritaire dans la structure de données . Vous pouvez essayer l'exemple pour renforcer vos connaissances sur la structure des données.

Si vous êtes curieux d'en savoir plus sur la science des données, consultez le programme Executive PG en science des données de IIIT-B & upGrad qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, 1 -on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.

Apprenez des cours de science des données en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

Quelles sont les applications d'une file d'attente prioritaire ?

La file d'attente prioritaire est une file d'attente spéciale où les éléments sont insérés en fonction de leur priorité. Cette fonctionnalité s'avère utile dans la mise en œuvre de diverses autres structures de données. Voici quelques-unes des applications les plus populaires de la file d'attente prioritaire :
 1. Algorithme du chemin le plus court de Dijkstra : la file d'attente prioritaire peut être utilisée dans l'algorithme du chemin le plus court de Dijkstra lorsque le graphe est stocké sous la forme d'une liste de contiguïté.
 2. Algorithme de Prim : l'algorithme de Prim utilise la file d'attente prioritaire pour les valeurs ou les clés des nœuds et extrait le minimum de ces valeurs à chaque étape.
 Compression des données : les codes Huffman utilisent la file d'attente prioritaire pour compresser les données.
 Systèmes d'exploitation : la file d'attente prioritaire est très utile pour les systèmes d'exploitation dans divers processus tels que l'équilibrage de charge et la gestion des interruptions.

Quelle approche est utilisée dans la mise en œuvre de la file d'attente prioritaire à l'aide d'un tableau ?

L'approche utilisée dans la mise en œuvre de la file d'attente prioritaire à l'aide d'un tableau est simple. Une structure est créée pour stocker les valeurs et la priorité de l'élément, puis le tableau de cette structure est créé pour stocker les éléments. Les opérations suivantes sont impliquées dans cette implémentation :
 1. enqueue() - Cette fonction insère les éléments à la fin de la file d'attente.
 2. peek() - Cette fonction parcourt le tableau pour renvoyer l'élément avec la priorité la plus élevée. S'il trouve deux éléments ayant la même priorité, il renvoie l'élément de valeur la plus élevée parmi eux.
 3. dequeue() - Cette fonction décalera tous les éléments, 1 position à gauche de l'élément renvoyé par la fonction peek() et diminuera la taille.

Quelle est la différence entre le tas max et le tas min ?

Ce qui suit illustre la différence entre le tas max et le tas min.
 Min Heap - Dans un min-heap, la clé du nœud racine doit être inférieure ou égale aux clés de son nœud enfant. Il utilise la priorité croissante. Le nœud avec la plus petite clé est prioritaire. Le plus petit élément est dépilé avant tout autre élément.
 Max Heap - Dans un max heap, la clé du nœud racine doit être supérieure ou égale à la clé des nœuds de ses enfants. Il utilise la priorité décroissante. Le nœud avec la plus grande clé est prioritaire. Le plus grand élément est dépilé avant tout autre élément.