Priority Queue

Eine Priority Queue (Prioritätswarteschlange) ist eine abstrakte Datenstruktur, die ähnlich wie eine reguläre Warteschlange (Queue) arbeitet, jedoch mit dem Unterschied, dass jedem Element eine Priorität zugewiesen wird. Elemente werden basierend auf ihrer Priorität verwaltet, sodass das Element mit der höchsten Priorität immer an erster Stelle für die Entnahme steht, unabhängig von der Reihenfolge, in der die Elemente hinzugefügt wurden. Hier sind die grundlegenden Konzepte und Funktionsweisen einer Priority Queue:

Grundprinzipien einer Priority Queue

1. Elemente und Prioritäten: Jedes Element in einer Priority Queue hat eine zugewiesene Priorität. Die Priorität kann durch ein numerisches Wert oder durch andere Kriterien festgelegt werden.
2. Entnahme nach Priorität: Die Entnahme (Dequeue) von Elementen erfolgt nicht nach dem First-In-First-Out (FIFO)-Prinzip wie in einer regulären Queue, sondern nach der Priorität der Elemente. Das Element mit der höchsten Priorität wird zuerst entnommen.
3. Einfügen (Enqueue): Beim Einfügen von Elementen wird die Position des neuen Elements basierend auf seiner Priorität bestimmt.

Implementierungen einer Priority Queue

1. Heap:

   • Min-Heap: Ein Min-Heap ist eine binäre Baumstruktur, bei der das kleinste Element (höchste Priorität) an der Wurzel steht. Jeder Elternknoten hat einen Wert kleiner oder gleich dem seiner Kinder.
   • Max-Heap: Ein Max-Heap ist eine binäre Baumstruktur, bei der das größte Element (höchste Priorität) an der Wurzel steht. Jeder Elternknoten hat einen Wert größer oder gleich dem seiner Kinder.
   • Operationen: Insertion (Einfügen) und extraction (Entnahme des höchsten/kleinsten Elements) haben beide eine Zeitkomplexität von O(log n), wo n die Anzahl der Elemente ist.

2. Verkettete Liste:

   • Elemente können in eine sortierte verkettete Liste eingefügt werden, wobei die Einfügeoperation O(n) Zeit benötigt. Das Entfernen des höchsten Prioritätselements kann jedoch in O(1) Zeit erfolgen.

3. Balancierte Bäume:

   • Datenstrukturen wie AVL-Bäume oder Rot-Schwarz-Bäume können ebenfalls verwendet werden, um eine Priority Queue zu implementieren. Diese bieten balancierte Baumstrukturen, die effiziente Einfüge- und Entnahmeoperationen ermöglichen.

Anwendungen von Priority Queues

1. Dijkstra's Algorithmus: Priority Queues werden verwendet, um die kürzesten Wege in einem Graphen zu finden.
2. Huffman-Codierung: Priority Queues werden verwendet, um ein optimaler Präfix-Codesystem zu erstellen.
3. Task Scheduling: Betriebssysteme verwenden Priority Queues, um Prozesse basierend auf ihrer Priorität zu planen.
4. Simulationssysteme: Ereignisse werden basierend auf ihrer Priorität oder ihrem Zeitpunkt verarbeitet.

Beispiel einer Priority Queue in Python

Hier ist ein einfaches Beispiel einer Priority Queue-Implementierung in Python unter Verwendung des heapq-Moduls, das einen Min-Heap bietet:

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))
    
    def pop(self):
        return heapq.heappop(self.heap)[1]
    
    def is_empty(self):
        return len(self.heap) == 0

# Beispielnutzung
pq = PriorityQueue()
pq.push("task1", 2)
pq.push("task2", 1)
pq.push("task3", 3)

while not pq.is_empty():
    print(pq.pop())  # Ausgabe: task2, task1, task3

In diesem Beispiel hat task2 die höchste Priorität (geringste Zahl) und wird daher zuerst ausgegeben.

Zusammenfassung

Eine Priority Queue ist eine nützliche Datenstruktur für Anwendungen, bei denen Elemente nach ihrer Priorität verwaltet werden müssen. Sie bietet effiziente Einfüge- und Entnahmeoperationen und kann mit verschiedenen Datenstrukturen wie Heaps, verketteten Listen und balancierten Bäumen implementiert werden.