AuK/Prioritätswarteschlangen SS12

Wiki-Quelltext dieser Seite.

<language>Java</language>
<language>Java</language>
=Einführung=
kurze Einführung


==Heaps==
was sind Heaps

 Max-Heapify(A,i)
 l<math>\leftarrow</math>Left(i)
 r<math>\leftarrow</math>Right(i)
 '''if''' l <math>\leq</math> heap-größe[A] und A[l] > A[i]
   '''then''' maximum <math>\leftarrow</math> l
   '''else''' maximum <math>\leftarrow</math> i
 '''if''' r <math>\leq</math> heap-größe[A] und A[r] > A[maximum]
   then maximum <math>\leftarrow</math>r
 '''if''' maximum <math>\neq</math> i
   '''then''' vertausche A[i] <math>\leftrightarrow</math> A[maximum]
        Max-Heapify(A,maximum)



===Übungsaufgaben===

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

=Normale Warteschlangen=
Normale Warteschlangen funktionieren nach dem FiFo-Prinzip (First in, first out).

<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(){
  System.out.print("[");
   for(Object element : elements){
    System.out.print(element+", ");
   }
  System.out.print("]");
  System.out.println("");
  }

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

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

=Prioritätswarteschlangen=
warum wieso wesshalb man die brauch und unter welchen umständen man die dem normalen vorziehen sollte

==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,


====Übungsaufgaben====