Prioritätswarteschlangen: Difference between revisions
m (→Prioritätswarteschlangen: typo) |
|||
Line 1: | Line 1: | ||
==Prioritätswarteschlangen== | ==Prioritätswarteschlangen== | ||
Prioritätswarteschlangen verwendet man, wenn man in einem Container wiederholt das jeweils kleinste (Min Priority Queue) oder größte (Max Priority Queue) Element finden und gewöhnlich auch aus dem Container entfernen muss. Die typische Schnittstelle einer Prioritätswarteschlange <tt>pq</tt> enthält also typischerweise folgende effizient implementierte Operationen: | |||
;Max Priority Queue: | |||
pq.insert(x) # Element x einfügen | |||
x = pq.largest() # das aktuell größte Element zurückgeben (aber es bleibt in der Queue) | |||
pq.removeLargest() # das aktuell größte Element entfernen | |||
Min Priority Queue: | |||
pq.insert(x) # Element x einfügen | |||
x = pq.smallest() # das aktuell kleinste Element zurückgeben (aber es bleibt in der Queue) | |||
pq.removeSmallest() # das aktuell kleinste Element entfernen | |||
Die Funktionen <tt>insert</tt> und <tt>remove</tt> werden auch oft mit <tt>push</tt> bzw. <tt>pop</tt> bezeichnet (wie beim Stack). In vielen Implementationen gibt <tt>remove</tt> außerdem das aktuelle größte bzw. kleinste Element zurück. Neben Min und Max Queue gibt es auch die '''bidirektionale Prioritätswarteschlange''', die das kleinste ''und'' das größte Element effizient finden und entfernen kann. | |||
===Prioritätswarteschlange als Suchproblem=== | ===Prioritätswarteschlange als Suchproblem=== | ||
Am einfachsten kann eine Prioritätswarteschlange durch sequentielle Suche realisiert werden. In diesem Fall ist einfach ein (unsortiertes) dynamisches Array <tt>a</tt> gegeben, dessen Elemente mit Prioritäten ausgestattet sind. Dann gilt | |||
pq.insert(x)<=> a.append(x) (amortisierte Komplexität <math>\mathcal{O}(1)</math>) | |||
Die Suche (in diesem Fall nach dem Element mit ''maximaler'' Priorität) wird durch sequenzielles Durchlaufen des Arrays realisiert | |||
def largest(a): | |||
N = len(a) | |||
if N == 0: | |||
raise RuntimeError("Access to empty priority queue.") | |||
max = a[0] | |||
k = 0 | |||
for n in range(1, N): # Dieser Code entspricht der inneren Schleife von Selection Sort | |||
if a[n] > max: # Die Suche hat also die Komplexität O(N). | |||
max = a[n] | |||
k = n | |||
return k # Den Index des kleinsten Elements zurückgeben | |||
Ähnlich implementiert man das Entfernen des größten Elements: Man sucht zunächst dessen Index, schiebt dann alle nachfolgenden Elemente um einen Index nach vorn, und verkürzt schließlich das dynamische Array um ein Element. | |||
Alternativ kann man auch die Komplexität von <tt>insert</tt> und <tt>largest</tt> vertauschen: <tt>insert</tt> kann die Queue sortiert aufbauen (indem jedes neue Element an seinem richtigen Platz eingefügt wird, was einen Aufwand von O(N) verursacht, da man im Mittel N/2 Elemente einen Platz nach hinten verschieben muss), so dass bei <tt>largest</tt> einfach in O(1) auf das letzte Element des Array zugegriffen wird. Auch das Entfernen des größten, also letzten Elements hat jetzt die amortisierte Komplexität O(1). | |||
Bei kleinen Arrays ist die sequentielle Suche die schnellste Methode. Bei großen Arrays hingegen ist die Suche mit O(N) nicht effizient. | |||
===Prioritätssuche mit einem binären (balancierten) Suchbaum=== | |||
Ein binärer Suchbaum eignet sich offensichtlich für die Prioritätssuche, weil das Einfügen und Entfernen eines Elements sowie die Suche nach dem kleinsten oder größten jeweils in <math>\mathcal{O}(\log N)</math> realisiert werden kann, falls der Baum balanciert ist. Man implementiert also <tt>insert</tt> z.B. wie beim [[Suchen#Andersson-B%C3%A4ume|Andersson-Baum]]. | |||
def largest( | def largest(node): # node istr die Wurzel des zu durchsuchenden Teilbaums | ||
if node.right is not None: # rechts stehen immer die großen Elemente | |||
return largest(node.right) # => Rekursion in den rechten Teilbaum | |||
return node # wenn es nicht mehr nach rechts geht, dann haben wir den größten Knoten gefunden | |||
Diese Funktion hat, wie auch <tt>insert</tt> und <tt>remove</tt>, die Komplexität <math>\mathcal{O}(\log N)</math>. Alle Funktionen sind somit für große Datenstrukturen sehr effizient. Allerdings stellt sich heraus, dass die Datenstruktur eines balancierten Suchbaums viel komplizierter ist, als für die Prioritätssuche notwendig ist. | |||
insert | |||
===Heap=== | ===Heap=== | ||
*Datenstruktur optimiert für Prioritätssuche - man sucht nicht effizient alle Knoten, sondern nur einen bestimmten z.B. Heap max<br> | *Datenstruktur optimiert für Prioritätssuche - man sucht nicht effizient alle Knoten, sondern nur einen bestimmten z.B. Heap max<br> |
Revision as of 19:10, 8 July 2008
Prioritätswarteschlangen
Prioritätswarteschlangen verwendet man, wenn man in einem Container wiederholt das jeweils kleinste (Min Priority Queue) oder größte (Max Priority Queue) Element finden und gewöhnlich auch aus dem Container entfernen muss. Die typische Schnittstelle einer Prioritätswarteschlange pq enthält also typischerweise folgende effizient implementierte Operationen:
- Max Priority Queue
pq.insert(x) # Element x einfügen x = pq.largest() # das aktuell größte Element zurückgeben (aber es bleibt in der Queue) pq.removeLargest() # das aktuell größte Element entfernen
Min Priority Queue:
pq.insert(x) # Element x einfügen x = pq.smallest() # das aktuell kleinste Element zurückgeben (aber es bleibt in der Queue) pq.removeSmallest() # das aktuell kleinste Element entfernen
Die Funktionen insert und remove werden auch oft mit push bzw. pop bezeichnet (wie beim Stack). In vielen Implementationen gibt remove außerdem das aktuelle größte bzw. kleinste Element zurück. Neben Min und Max Queue gibt es auch die bidirektionale Prioritätswarteschlange, die das kleinste und das größte Element effizient finden und entfernen kann.
Prioritätswarteschlange als Suchproblem
Am einfachsten kann eine Prioritätswarteschlange durch sequentielle Suche realisiert werden. In diesem Fall ist einfach ein (unsortiertes) dynamisches Array a gegeben, dessen Elemente mit Prioritäten ausgestattet sind. Dann gilt
pq.insert(x)<=> a.append(x) (amortisierte Komplexität <math>\mathcal{O}(1)</math>)
Die Suche (in diesem Fall nach dem Element mit maximaler Priorität) wird durch sequenzielles Durchlaufen des Arrays realisiert
def largest(a): N = len(a) if N == 0: raise RuntimeError("Access to empty priority queue.") max = a[0] k = 0 for n in range(1, N): # Dieser Code entspricht der inneren Schleife von Selection Sort if a[n] > max: # Die Suche hat also die Komplexität O(N). max = a[n] k = n return k # Den Index des kleinsten Elements zurückgeben
Ähnlich implementiert man das Entfernen des größten Elements: Man sucht zunächst dessen Index, schiebt dann alle nachfolgenden Elemente um einen Index nach vorn, und verkürzt schließlich das dynamische Array um ein Element.
Alternativ kann man auch die Komplexität von insert und largest vertauschen: insert kann die Queue sortiert aufbauen (indem jedes neue Element an seinem richtigen Platz eingefügt wird, was einen Aufwand von O(N) verursacht, da man im Mittel N/2 Elemente einen Platz nach hinten verschieben muss), so dass bei largest einfach in O(1) auf das letzte Element des Array zugegriffen wird. Auch das Entfernen des größten, also letzten Elements hat jetzt die amortisierte Komplexität O(1).
Bei kleinen Arrays ist die sequentielle Suche die schnellste Methode. Bei großen Arrays hingegen ist die Suche mit O(N) nicht effizient.
Prioritätssuche mit einem binären (balancierten) Suchbaum
Ein binärer Suchbaum eignet sich offensichtlich für die Prioritätssuche, weil das Einfügen und Entfernen eines Elements sowie die Suche nach dem kleinsten oder größten jeweils in <math>\mathcal{O}(\log N)</math> realisiert werden kann, falls der Baum balanciert ist. Man implementiert also insert z.B. wie beim Andersson-Baum.
def largest(node): # node istr die Wurzel des zu durchsuchenden Teilbaums if node.right is not None: # rechts stehen immer die großen Elemente return largest(node.right) # => Rekursion in den rechten Teilbaum return node # wenn es nicht mehr nach rechts geht, dann haben wir den größten Knoten gefunden
Diese Funktion hat, wie auch insert und remove, die Komplexität <math>\mathcal{O}(\log N)</math>. Alle Funktionen sind somit für große Datenstrukturen sehr effizient. Allerdings stellt sich heraus, dass die Datenstruktur eines balancierten Suchbaums viel komplizierter ist, als für die Prioritätssuche notwendig ist.
Heap
- Datenstruktur optimiert für Prioritätssuche - man sucht nicht effizient alle Knoten, sondern nur einen bestimmten z.B. Heap max
- Definition: ein linkslastiger Binärbaum ist ein Baum mit <math>d(node.left) \geq d(node.right)</math>
Ein Heap ist ein linkslastiger, perfekt balancierter Baum. (lässt sich max. um 1 unterscheiden)
Man kann einen Heap leicht als Array implementieren, wie folgende Grafik veranschaulicht:
index[parent] = [(indexChild - 1)/2] #[] heißt abgerundet
index[left] = index[parent]2 + 1
index[right] = index[parent]2 + 2
=> linkslastiger perfect balancierter Binärbaum kann effizient als Array abgespeichert werden
=>verwende Indizes wie oben
Heap - Bedingung
- die Wurzel hat höhere Prioriät als die Kinder(gilt für jeden Teilbaum)
=>Wurzel = array[0] hat die größte Priorität
def largest(h):
return h[0] <math>\mathcal{O}(N)</math>
Einfügen in einem Heap
h - Array #speichrt Haep
def insert(h,x):
h.append(x) # wir speichern den Wurzel am Ende, so wird glecih zu einem linkslastigen perfect balancierten Baum (die Haep - Bedingung ist erfüllt)
upheap(h, len(h) - 1):
def upheap(h, k):
"""k-tes Element evtl. an der falsche Stelle
"""
v = h[k]
while True #endlose Schleife
if k == 0:
break
parent = (k - 1)/2
if h[parent]>v:
break
h[k] = h[parent]
k = parent
h[k] = v
def removeLargest(h): h[0] = h[len(h) - 1]
del h[len(n) - 1] <math>\mathcal{O}(1)</math>
downHeap(h, 0) <math>\mathcal{O}(logN)</math>
def downHeap(h, k):
v = h[k]
while True
child = 2k + 1 #linke Kind
if child <math>\ge</math>len(h):
break
if child < h[child] < h[child + 1] #rechtes Kind
child = child + 1 if v <math>\ge</math> h[child]:
break
h[k] = h[child]
k = child
h[k] = v
Beispiel am Wort "SORTING"
(Grafiken folgen)
weitere Heapvarianten
- Min-Max-Priority Queue ("Deap", Double Ended Heap)
- Binomialer Heap, effiziente Operation "merege Heap" <math>\mathcal{O}(n * log N (i*N_1 + N_2)</math>
(Beweis durch binomiale Koeffizienten, Zusammenführen zweier Prioritätslisten)
- Fibonacci-Heap, einfügen in amortisierter Zeit <math>\mathcal{O}(1)</math>
(Beweis durch Fibonacci Zahlen)