Vorlesung Informatik 2 - Teil B: Theorie
4.15 Heap
Ein Heap ist ein fast vollständiger Binärbaum, bei der für den jeden Knoten gilt, dass er kleiner (größer) oder gleich als seine Kinder ist.
Wenn die Heap Bedingung kleiner oder gleich ist, spricht man von einem min-Heap, bei größer gleich von einem max-Heap.
Wie bei einem Suchbaum müssen die Knoten also wieder einen Schüssel enthalten, der vergleichbar ist (Java: Comparable). Die Heap-Bedingung ist aber schwächer als die Suchbaum-Bedingung. Und ein Heap ist keine Map, es kann doppelte Schlüssel geben.
Als Konsequenz ist die Wurzel in einem Heap immer das kleinste (größte) Element.
Die abstrakte Datenstruktur, die ein Heap implementiert ist eine Queue, wir definieren also wieder die beiden Methoden offer und poll.
Die Heap-Bedingung sorgt zusätzliche dafür, dass die Elemente der Queue nicht in der Reihenfolge des Einfügens, sondern nach der Größe ihrer Schlüssel entfernt werden.
Dieses Verhalten wird auch Priority-Queue oder Prioritätswarteschlange genannt, da die Schlüsselwerte oft als Prioritäten interpretiert werden.
Typische Anwendungen von Heaps sind:
- Verwaltung von Ressourcen wie z.B. rechenwillige Prozesse, I/O Kanäle, Speicherzugriffe, Druckerwarteschlangen, Load-Balancing in Netzen u.s.w.
- Die Klasse gieriger Algorithmen (Greedy Algorithm) verwenden häufig Prioritätswarteschlangen. Zu diesen Algorithmen gehören z.B Gradientenverfahren um lokale Minima einer Funktion zu finden, Sukzessive Einbindung zur Lösung diskreter Optimierungsprobleme, Wegfindung und spannende Bäume in Graphen, ...
- Spiele haben oft Mechanismen, bei denen eine Prioritätswarteschlange zum Einsatz kommt, z.B. die Zuteilung in Räume bei League of Legends oder PlayerUnknown's Battlegrounds.
- Das Verfahren für die Zuteilung von Studienplätzen und ähnliche Mechanismen basieren ebenfalls auf Prioritätswarteschlangen.
Implementierung für einen min-Heap:
Die offer Methode funktioniert so:
- füge das neue Element an die nächste freie Stelle im Baum, also in die letzte unterste Schicht an die nächste Position oder als erstes Element in eine neue Schicht.
- Vertausche das neue Element so lange mit seinem Vaterknoten, bis die Heap-Bedingung erfüllt ist. Diese Operation wird up-heap genannt.
Die poll Methode besteht aus folgenden Schritten:
- entferne die Wurzel, deren Inhalt ja als nächstes an der Reihe ist.
- Entferne das letzte Element im Baum und füge an Stelle der Wurzel ein
- Vertausche die Wurzel solange mit ihrem kleinsten Kind, bis die Heap-Bedingung erfüllt ist (down-heap).
offer und poll haben beide die Komplexität O(log N), da up-Heap und down-Heap jeweils einem absoluten Pfad folgen.
Wenn der Baum mit Hilfe eines Arrays implementiert ist, sind diese Methoden besonders effizient, da das letzte Element im Baum das letzte Element des Arrays ist und.
Beispiel:
Implementierung:
class Heap<T>{
class HeapKnoten{ // Hilfsklasse,
int prio;
T inhalt;
HeapKnoten(int prio, T x){
this.prio = prio;
this.inhalt = x;
} // ENDE innere Klasse HeapKnoten
private int laenge = 0;
private HeapKnoten<T>[] knoten = new HeapKnoten[1000];
public offer(int prio, T x){
knoten[++laenge] = new HeapKnoten(prio, x);
upHeap();
}
private void upHeap(){
int ix=laenge;
while(ix>1 && knoten[ix].prio<knoten[ix/2].prio){
tausche(knoten, ix, ix/2);
ix/=2;
}
}