Structure de données - File de priorité
Une file de priorité est une extension de la file. Contrairement au « premier entré, premier sorti » d'une file normale, chaque élément d'une file de priorité se voit attribuer une priorité, et l'opération de retrait supprime toujours l'élément ayant la priorité la plus élevée dans la file actuelle.
Concept et caractéristiques de la file de priorité
On peut la comparer au système de triage des urgences d'un hôpital — plus l'état d'un patient est critique, plus tôt il est traité, même s'il arrive plus tard.
Les opérations principales d'une file de priorité sont différentes de celles d'une file normale :
| Opération | File normale | File de priorité |
|---|---|---|
| Enfiler | Ajouter un élément à l'arrière | Insérer un élément avec une priorité |
| Défiler | Retourner l'élément en tête (le premier enfilé) | Retourner l'élément ayant la priorité la plus élevée |
Comparaison de trois méthodes d'implémentation
Tableau non ordonné
Liste chaînée ordonnée
Tas ★ Recommandé
L'implémentation par tas est optimale : elle équilibre l'efficacité d'insertion et de retrait, et est une dépendance essentielle d'algorithmes tels que le plus court chemin de Dijkstra et le codage de Huffman.
La figure ci-dessus compare les différences de complexité temporelle des trois méthodes d'implémentation ; l'implémentation par tas est le choix le plus équilibré.
Implémentation basée sur un tableau non ordonné
Exemple
#define MAX 100
/* File de priorité basée sur un tableau non ordonné (file de priorité max : plus la valeur est grande, plus la priorité est élevée) */
struct PriorityQueue {
int items[MAX];
int size; /* Nombre actuel d'éléments */
};
void initPQ(struct PriorityQueue* pq) { pq->size = 0; }
/* Enfiler : ajouter directement à la fin, O(1) */
void enqueue(struct PriorityQueue* pq, int value) {
if (pq->size >= MAX) return;
pq->items[pq->size++] = value;
}
/* Défiler : parcourir pour trouver le maximum, O(n)
Après l'avoir trouvé, déplacer le dernier élément à la position supprimée, et décrémenter la taille de 1 */
int dequeue(struct PriorityQueue* pq) {
if (pq->size == 0) return -1;
/* Trouver l'indice de la valeur maximale */
int maxIdx = 0;
for (int i = 1; i < pq->size; i++) {
if (pq->items[i] > pq->items[maxIdx]) {
maxIdx = i;
}
}
int maxVal = pq->items[maxIdx];
/* Déplacer le dernier élément vers la position supprimée (éviter un grand nombre de déplacements) */
pq->items[maxIdx] = pq->items[--pq->size];
return maxVal;
}
int main() {
struct PriorityQueue pq;
initPQ(&pq);
enqueue(&pq, 5);
enqueue(&pq, 9);
enqueue(&pq, 3);
enqueue(&pq, 7);
printf("Défiler (priorité la plus élevée) : %d\n", dequeue(&pq)); /* Sortie : 9 */
printf("Défiler (priorité la plus élevée) : %d\n", dequeue(&pq)); /* Sortie : 7 */
printf("Défiler (priorité la plus élevée) : %d\n", dequeue(&pq)); /* Sortie : 5 */
printf("Défiler : %d\n", dequeue(&pq)); /* Sortie : 3 */
return 0;
}
Implémentation basée sur une liste chaînée ordonnée
Exemple
#include <stdlib.h>
struct Node {
int data;
int priority; /* Priorité (plus la valeur est grande, plus la priorité est élevée) */
struct Node* next;
};
/* Enfiler : insérer par ordre décroissant de priorité, O(n) */
struct Node* enqueue(struct Node* head, int data, int priority) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;
/* Liste vide ou le nouveau nœud a la plus haute priorité → insérer en tête */
if (head == NULL || head->priority < priority) {
newNode->next = head;
return newNode;
}
/* Parcourir pour trouver la position appropriée (conserver l'ordre décroissant) */
struct Node* cur = head;
while (cur->next != NULL && cur->next->priority >= priority) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
return head;
}
/* Défiler : supprimer le nœud de tête (priorité la plus élevée), O(1) */
struct Node* dequeue(struct Node* head) {
if (head == NULL) return NULL;
struct Node* temp = head;
printf("Défiler : donnée=%d, priorité=%d\n", temp->data, temp->priority);
head = head->next;
free(temp);
return head;
}
int main() {
struct Node* pq = NULL;
pq = enqueue(pq, 10, 1); /* Donnée 10, priorité 1 */
pq = enqueue(pq, 20, 5); /* Donnée 20, priorité 5 */
pq = enqueue(pq, 30, 3); /* Donnée 30, priorité 3 */
pq = dequeue(pq); /* Retrait : data=20, priority=5 (priorité la plus élevée) */
pq = dequeue(pq); /* Retrait : data=30, priority=3 */
pq = dequeue(pq); /* Retrait : data=10, priority=1 */
return 0;
}
TasC'est actuellement la solution la plus courante et la plus équilibrée pour implémenter des files de priorité—l'insertion et la suppression de l'élément de plus haute priorité s'effectuent toutes deux en temps O(log n). Ce contenu sera détaillé au chapitre 15 sur les tas.
Scénarios d'application
| Scénario | Description |
|---|---|
| Ordonnancement des tâches | Le système d'exploitation détermine l'ordre d'exécution du CPU en fonction de la priorité des tâches. |
| Plus court chemin de Dijkstra | À chaque fois, sélectionnez le nœud non visité ayant la plus petite distance, en vous appuyant sur une file de priorité. |
| Codage de Huffman | Extraire de façon répétée les deux nœuds ayant la fréquence la plus faible et les fusionner pour construire un arbre de codage optimal. |