Inhaltsverzeichnis
Prioritätswarteschlangen
Anwendungsbeispiele für Prioritätswarteschlangen:
Aufbau und Unterhaltung einer Datenstruktur,
Die Operation replace entspricht fast einem insert,
Elementare Implementationen
static int a [maxN + 1], N;
Die Operation construct ist lediglich eine Feldkopie
Eine andere elementare Form der Organisation,
Anstelle der oben angegebenen Implementation mit Hilfe
Die Datenstruktur des Heaps
Diese Struktur kann erzeugt werden, in dem ein Knoten
Darstellung eines Heaps als vollständiger Baum
Darstellung eines Heaps als Feld
Alle Algorithmen operieren entlang eines Pfades (path)
Algorithmen mit Heaps
Einfügen eines neuen Elements ( P ) in einen Heap
Aufbau eines Heaps
Beispiel-Programm
Die replace-Operation erfordert das Ersetzen des Schlüssels
Weitere Implementationen sind:
Bei der remove-Operation wird folgende Implementation
Eigenschaften des Heap:
Heapsort
heapsort (int a [], int N )
Vollständiger Heap ,
remove kann implementiert werden,
Eigenschaft: Bottom Up Aufbau eines Heaps erfolgt in linearer Zeit.
Eigenschaft: Heapsort benötigt für das Sortieren von
Indirekte Heaps
Indirekte Heap-Datenstrukturen
Weiterentwickelte Implementationen der join-Operation
|