| Einsatz
von Heapsort
Häufig ist es so, daß man nur einzelne Teile des Heapsortalgorithmus
einsetzt:
Heaps sind beispielsweise hervorragend zur Implementierung von priorisierten
Warteschlangen geeignet. Eine priorisierte Warteschlange ist eine Reihung
von Objekten nach dem "largest in, first out" Prinzip. Das bedeutet, ein
Element, das hinten an die Warteschlange angefügt wird, kommt um so
früher "dran", je größer seine Dringlichkeit ist.
Angewandt wird dieses Prinzip z. B. bei:
-
Betriebssystemen, die Job-Scheduling betreiben
-
in Aufzugssteuerungen.
Gewöhnlich werden Warteschlangen, z.B. Print-Queues einfach durch
lineare Listen verwirklicht. Die Elemente, die eingefügt werden sollen,
werden dann nach ihrer Dringlichkeit in diese Liste einsortiert. In einer
Schlange der Größe
n ist dabei
für jede Einfüge- bzw. Entfernenoperation der Aufwand linear.
Dies ist dann für große Warteschlangen sehr zeitraubend.
Die Effizienz einer priorisierten Warteschlange läßt sich
allerdings deutlich steigern, wenn
man sie in Form eines Heaps organisiert.
Für das Einfügen oder Entfernen eines Elements sind dann nur
maximal log(n) Schritte erforderlich.
Soll ein neues Element anfgefügt werden, so setzt man es einfach
an das untere Ende des Heaps und läßt es solange aufsteigen,
bis die Heapeigenschaft wiederhergestellt ist.
Beim Entfernen eines Elements greift man einfach auf die Wurzel
des Heaps zu.
Ansonsten kann Heapsort auch zum Optimieren externer Sortierverfahren
eingesetzt werden.
|
