Prioritätswarteschlangen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-04-11T08:33:44+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einführung: binäre Heaps
- 1.1 Arten binärer Heaps
- 1.2 Grundlegende Operationen
  - 1.2.1 Max-Heapify
2 Prioritätswarteschlangen
- 2.1 Nicht Adressierbare Prioritätswarteschlangen
  - 2.1.1 Binary Heaps
- 2.2 Adressierbare Prioritätswarteschlangen

Einführung: binäre Heaps

Da bei Prioritätswarteschlangen die Datenstruktur des Heaps verwendet wird ist es zunächst notwendig diese zu einzuführen. Zum besseren Verständis beim Umgang mit Heaps wird der Heapsort Algorithmus erläutert. Ein binärer Heap kann als ein fast vollständiger binärer Baum angesehen werden. Jeder Knoten entspricht dabei einem Element des Feldes. Die niedrigste Ebene des Baumes ist von links her bis zu einem bestimmten Punkt, der Rest vollständig gefüllt. Ist A ein Feld, dass einen Heap repräsentiert, dann hat es zwei Eigenschaften: länge[A], die Anzahl der Elemente des Feldes, und heap-größe[A], die Anzahl der Elemente im Heap. Es ist also kein Element hinter A[heap-größe(A)] mit heap-größe[A] \leq länge[A] ein Element des Heaps. Die Wurzel des Baumes ist A[1]. Bei gegebenem Index i lassen sich die Indizes des Vaters Vater(i) und die des rechten und linken Kindes Right(i), bzw. Left(i) berechnen.

Vater(i)
\lfloor return' i/2 \rfloor

Right(i)
return 2i

Left(i)
return 2i+1

Die Höhe eines Knoten ist als die Anzahl der Kanten des längsten einfachen absteigenden Pfades zu einem Blatt definiert. Die Höhe des Heaps ist die Höhe seiner Wurzel. Ein Heap mit n Elementen hat die Höhe \theta(lg n), da er auf einem vollständigen binären Baum basiert.

Arten binärer Heaps

Es gibt zwei Arten binärer Heaps: Max-Heaps und Min-Heaps. Beide erfüllen eine spezifische Heap-Eigenschaft. Die Max-Heap-Eigenschaft besteht darin, dass für jeden Knoten i außer der Wurzel gilt: A[Vater(i)] \geq A[i], d.h. der Wert eines Knotens ist stets höchstens so groß, wie der seines Vaters. In einem Max-Heap liegt das größte Element also in der Wurzel.

Ein Min-Heap ist entgegengesetzt aufgabaut. Hier gilt: A[Vater(i)] \leq A[i]. Hier liegt in der Wurzel das kleinste Element. Für Heapsort werden Max-Heaps verwendet, für Prioritätswarteschlangen Min-Heaps.

Grundlegende Operationen

Max-Heapify

Sorgt für die Aufrechterhaltung der Heap-Eigenschaft. Erhält ein Feld A und einen Index i. Es wird angenommen, dass die Bäume, die von Left(i) und Right(i) ausgehen die Max-Heap-Eigenschaft erfüllen, A[i] dagegen kann kleiner als seine Kinder sein, was die Heap-Eigenschaft verletzen würde. Max-Heapify lässt den Wert von A[i] im Heap nach unten sinken, sodass der von i ausgehende Teilbaum zu einem Max-Heap wird.

Max-Heapify(A,i)
l\leftarrowLeft(i)
r\leftarrowRight(i)
if l \leq heap-größe[A] und A[l] > A[i]
  then maximum \leftarrow l
  else maximum \leftarrow i
if r \leq heap-größe[A] und A[r] > A[maximum]
  then maximum \leftarrowr
if maximum \neq i
  then vertausche A[i] \leftrightarrow A[maximum]
       Max-Heapify(A,maximum)

Abbildung

====Laufzeit====
Die Laufzeit setzt sich zusammen aus <math>\Theta(1)</math> um die Beziehungen zwischen ''A[i]'', ''A[Left(i)]'' und ''A[Right(i)]'' zu bestimmen, sowie der Zeit für
die Ausführung von Max-Heapify auf einen von ''i'' ausgehenden Teilbaum. Die von den Kindern ausgehenden Teilbäume haben höchstens die Größe <math>\frac{2n}{3}</math>.
Der schlechteste Fall tritt ein, wenn die letzte Ebene des Baumes exakt halb gefüllt ist.
Die Rekursionsgleichung <math>T(n) \leq T(\frac{2n}{3})+\Theta(1)</math> beschreibt die Laufzeit von Max-Heapify.
Nach dem Mastertheorem ist die Lösung <math>T(n)=O(lg (n))</math>. Die Laufzeit auf einen Knoten der Höhe ''h'' kann auch mit <math>O(h)</math> angegeben werden.



Build-Max-Heap erzeugt einen Max-Heap aus einem ungeordneten Feld <math>O(n)</math>

===Build-Heap===
Um ein Feld A[1..n] mit n=länge[A] in einen Max-Heap zu überführen kann die Prozedur Max-Heapify bottom-up angewendet werden.
Alle Elemente im Teilfeld A[(\lfloor n/2 \rfloor +1)..n] sind Blätter des Baumes, daher sind sie zu Beginn einelementige Heaps.
Build-Max-Heap durchläuft alle übrigen Knoten und führt dort Max-Heapify aus.

 Build-Max-Heap(A)
 heap-größe[A] <math>\leftarrow</math> länge[A]
 '''for''' i <math>\leftarrow \lfloor</math>länge[A]/2<math> \rfloor </math> '''downto''' 1
    '''do''' Max-Heapify(A,i)

<popup name="Klassen-Definitionen">
</popup>

Beweis für korrekte Arbeit

\TBD

==Übungsaufgaben==
*Mastertheorem
<popup name="Lösung">Ach, diese Aufgabe ist so einfach, da braucht ihr keine Lösung.</popup>
<br/>
*Was ist die maximale und minimale Anzahl von Elementen in einem Heap der Höhe h?
<popup name="Lösung">Ach, diese Aufgabe ist so einfach, da braucht ihr keine Lösung.</popup>
<br/>
*in max heap, wo kleinestes element, wenn alle paarweise verschieden
<popup name="Lösung">Ach, diese Aufgabe ist so einfach, da braucht ihr keine Lösung.</popup>
<br/>
*ist (blablabla) ein max heap?
<popup name="Lösung">Ach, diese Aufgabe ist so einfach, da braucht ihr keine Lösung.</popup>
<br/>
*Schleife statt Rekursion bei Max-Heapify
<popup name="Lösung">Ach, diese Aufgabe ist so einfach, da braucht ihr keine Lösung.</popup>
<br/>
*Max-Heapify(A,i), wenn A[i] größer als seine Kinder ist
<popup name="Lösung">Ach, diese Aufgabe ist so einfach, da braucht ihr keine Lösung.</popup>
<br/>

==Exkurs Heap-Sort==
kurzes blabla um an vorgänger an zu knüpfen

=Normale Warteschlangen=
[[Bild:HansV2_Queue.gif|gerahmt|Prozess des hinzufügens und herausnehmens von Elementen aus einer Warteschlange]]
Normale Warteschlangen funktionieren nach dem FiFo-Prinzip (First in, first out).
Es existieren verschiedene Formen der normalen Warteschlangen, z.B. dynamisch erweiterbare oder
Warteschlangen mit fester Größe.

Anwendung findet die normale Warteschlange vor allem bei verteilten Systemen bei bei der Synchronisation von Prozessen/Threads.
Dies lässt sich am Beispiel der Warteschlange bei Druckaufträgen vorstellen.
Wenn ein Druckauftrag gesendet wurde, der Drucker jedoch bereits in benutzung ist, so wird der Druckauftrag in eine Warteschlange gesteckt.
So kann der Drucker die anstehenden Aufträge seriell abarbeiten, ohne, dass der Nutzer warten muss bis der Drucker wieder frei ist.

Eine gute Analogie, um die normalen Warteschlangen zu beschreiben ist "Wer zuerst kommt malt zuerst" (oder in unserem Beispiel "druckt zuerst").



<popup name="Klassen-Definitionen">
<code id="35435435436546546">
public Object Queue(){
  private Object[] elements = new Object[0];
  
  public void enqueue(Object element){
    int length = elements.length;
    Object[] newElements = new Object[length+1];
    for(int i=0; i<= length-1; i++){
      newElements[i] = elements[i];
    }
    newElements[length] = element;
    elements = newElements;
  }

  public Object dequeue(){
    int length = elements.length;
    Object firstElement = elements[0];
    Object[] newElements = new Object[length-1];
    for(int i=0; i< length-1; i++){
      newElements[i] = elements[i+1];
    }
    elements = newElements; 
    return firstElement;
  }

  public void showElements(){
   String output = "[";
   for(Object element : elements){
    output += element+", ";
   }
  System.out.println(output.substring(0,output.length()-2)+"]");
  }

return this;
 }
</code>
</popup>

<run id="35435435436546546">
queue= Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.showElements();
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());

Prioritätswarteschlangen

Wie in der letzten Präsentation deutlich wurde ist Heapsort ein guter Algorithmus, wird aber von Quicksort geschlagen. Dennoch ist die Datenstruktur des Heaps sehr nützlich. Unter anderem bei Prioritätswarteschlangen. Wie bei Heaps gibt es auch hier zwei Varianten Max-Prioritätswarteschlangen und Min-Prioritätswarteschlangen. Im folgenden werden Min-Prioritätswarteschlangen verwendet.

Prioritätswarteschlange: Eine Prioritätswarteschlange ist eine Datenstruktur für die Speicherung einer Menge S, deren Elementen jeweils ein Wert zugeordnet ist, den man als Schlüssel bezeichnet.

Eine Min-Prioritätswarteschlange unterstützt folgende Grundoperationen:

Insert(S,x) fügt das Element x in die Menge S ein. Operation kann als S \leftarrow S \bigcup {x} geschrieben werden.

Minimum(S) gibt das Element mit dem kleinsten Schlüssel zurück

Extract-min entfernt das kleinste Element und gibt es zurück

build

Addressierbare Prioritätswarteschlangen unterstützen zusätzlich:

insert

remove(h) element mit handle h enfernen

decrease-key(S,x,k) verringert den Wert des Schlüssels von Element x auf den neuen Wert k, von dem angenommen wird, dass er genauso groß ist, wie der aktuelle wert.

Merge(M,Q) M:=M \bigcup Q; Q:=leere Menge

anwendungsbeispiel

\TBD

binary heaps können adressierbar sein aber dafür gibts bessere heaps

theorem 6.1 (S6) \TBD

Nicht Adressierbare Prioritätswarteschlangen

siehe prio-queues was hir rein soll

Binary Heaps

was ist das, wie funktioniert das?

Adressierbare Prioritätswarteschlangen

siehe prio-queues

Binominal Bäume

nochmal, aber spezieller

Pairing-heaps

wer wie was *clap* *clap*

Fibonacci-heaps

wieso wesshalb warum,

Prioritätswarteschlangen SS12

Inhaltsverzeichnis

Einführung: binäre Heaps

Arten binärer Heaps

Grundlegende Operationen

Max-Heapify

Prioritätswarteschlangen

Nicht Adressierbare Prioritätswarteschlangen

Binary Heaps

Adressierbare Prioritätswarteschlangen

Binominal Bäume

Pairing-heaps

Fibonacci-heaps

Übungsaufgaben

Suche