Datenstruktur - Prioritätswarteschlange
Eine Prioritätswarteschlange ist eine Erweiterung der Warteschlange. Anders als beim "First In, First Out" einer normalen Warteschlange wird jedem Element in einer Prioritätswarteschlange eine Priorität zugewiesen, und die Dequeue-Operation entfernt immer das Element mit der höchsten Priorität in der aktuellen Warteschlange.
Konzept und Merkmale der Prioritätswarteschlange
Man kann es mit dem Triagesystem in der Notaufnahme eines Krankenhauses vergleichen — je kritischer der Zustand eines Patienten, desto eher wird er behandelt, auch wenn er später ankommt.
Die Kernoperationen einer Prioritätswarteschlange unterscheiden sich von denen einer normalen Warteschlange:
| Aktion | Normale Warteschlange | Prioritätswarteschlange |
|---|---|---|
| Einreihen | Element am Ende hinzufügen | Element mit einer Priorität einfügen |
| Entnehmen | Element am Kopf zurückgeben (das zuerst eingereihte) | Element mit der höchsten Priorität zurückgeben |
Vergleich dreier Implementierungsmethoden
Ungeordnetes Array
Geordnete verkettete Liste
Heap ★ Empfohlen
Die Heap-Implementierung ist optimal: Sie balanciert die Effizienz von Einfügen und Entfernen aus und ist die zentrale Abhängigkeit von Algorithmen wie dem Dijkstra-Algorithmus für kürzeste Wege und der Huffman-Kodierung.
Die obige Abbildung vergleicht die Unterschiede in der Zeitkomplexität der drei Implementierungsmethoden; die Heap-Implementierung ist die ausgewogenste Wahl.
Implementierung basierend auf ungeordnetem Array
Beispiel
#define MAX 100
/* Prioritätswarteschlange basierend auf ungeordnetem Array (Max-Prioritätswarteschlange: Je größer der Wert, desto höher die Priorität) */
struct PriorityQueue {
int items[MAX];
int size; /* Aktuelle Anzahl der Elemente */
};
void initPQ(struct PriorityQueue* pq) { pq->size = 0; }
/* Enqueue: direkt am Ende anhängen, O(1) */
void enqueue(struct PriorityQueue* pq, int value) {
if (pq->size >= MAX) return;
pq->items[pq->size++] = value;
}
/* Dequeue: durchlaufen, um das Maximum zu finden, O(n)
Nachdem es gefunden wurde, das letzte Element an die entfernte Position verschieben und size um 1 dekrementieren */
int dequeue(struct PriorityQueue* pq) {
if (pq->size == 0) return -1;
/* Index des Maximalwerts finden */
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];
/* Das letzte Element an die gelöschte Position verschieben (um eine große Anzahl von Verschiebungen zu vermeiden) */
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("Dequeue (höchste Priorität): %d\n", dequeue(&pq)); /* Ausgabe: 9 */
printf("Dequeue (höchste Priorität): %d\n", dequeue(&pq)); /* Ausgabe: 7 */
printf("Dequeue (höchste Priorität): %d\n", dequeue(&pq)); /* Ausgabe: 5 */
printf("Entnehmen: %d\n", dequeue(&pq)); /* Ausgabe: 3 */
return 0;
}
Implementierung auf Basis einer geordneten verketteten Liste
Beispiel
#include <stdlib.h>
struct Node {
int data;
int priority; /* Priorität (je größer der Wert, desto höher die Priorität) */
struct Node* next;
};
/* Einreihen: in absteigender Reihenfolge der Priorität einfügen, 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;
/* Leere Liste oder der neue Knoten hat die höchste Priorität → am Kopf einfügen */
if (head == NULL || head->priority < priority) {
newNode->next = head;
return newNode;
}
/* Durchlaufen, um die passende Position zu finden (absteigende Reihenfolge beibehalten) */
struct Node* cur = head;
while (cur->next != NULL && cur->next->priority >= priority) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
return head;
}
/* Dequeue: Kopfknoten entfernen (höchste Priorität), O(1) */
struct Node* dequeue(struct Node* head) {
if (head == NULL) return NULL;
struct Node* temp = head;
printf("Dequeue: Daten=%d, Priorität=%d\n", temp->data, temp->priority);
head = head->next;
free(temp);
return head;
}
int main() {
struct Node* pq = NULL;
pq = enqueue(pq, 10, 1); /* Daten 10, Priorität 1 */
pq = enqueue(pq, 20, 5); /* Daten 20, Priorität 5 */
pq = enqueue(pq, 30, 3); /* Daten 30, Priorität 3 */
pq = dequeue(pq); /* Dequeue: data=20, priority=5 (höchste Priorität) */
pq = dequeue(pq); /* Dequeue: data=30, priority=3 */
pq = dequeue(pq); /* Dequeue: data=10, priority=1 */
return 0;
}
HeapDerzeit ist es die gebräuchlichste und ausgewogenste Lösung zur Implementierung von Prioritätswarteschlangen – sowohl das Einfügen als auch das Entfernen des Elements mit der höchsten Priorität erfolgen in O(log n) Zeit. Dieser Inhalt wird in Kapitel 15 über Heaps ausführlich behandelt.
Anwendungsszenarien
| Szenario | Beschreibung |
|---|---|
| Aufgabenplanung | Das Betriebssystem bestimmt die CPU-Ausführungsreihenfolge basierend auf der Priorität der Aufgabe. |
| Dijkstras kürzester Pfad | Wähle jedes Mal den unbesuchten Knoten mit der kleinsten Distanz aus und stütze dich dabei auf eine Prioritätswarteschlange. |
| Huffman-Kodierung | Entnehme wiederholt die beiden Knoten mit der niedrigsten Frequenz und führe sie zusammen, um einen optimalen Codierungsbaum aufzubauen. |