EINI-I
Einführung in die Informatik
für Naturwissenschaftler und
Ingenieure I
Kapitel 11
Claudio Moraga, Gisbert Dittrich
FBI Unido
[email protected]
Vorl “EINI-I"
Kap 11: Prioritätswarteschlange
Gliederung Kapitel 11
•
•
•
•
•
29.01.2001
Situation
Operationen
Realisierung über Feld(/verkettete Liste)
Laufzeitanalyse (grob)
Genauere Analyse
2
Vorl “EINI-I"
Kap 11: Prioritätswarteschlange
Situation
• Habe auf einem Prozessor eine Menge
wartender Aufträge
• Jedem Auftrag ist eine Priorität durch eine
Rangnummer zugeordnet,
– Je niedriger die Rangnummer, desto höher die
Priorität
• Der Auftrag mit der höchsten Priorität wird
zuerst abgearbeitet
– , also der mit der kleinsten Rangnummer
• Die Anzahl der Aufträge ist nach oben begrenzt.
29.01.2001
3
Vorl “EINI-I"
Kap 11: Prioritätswarteschlange
Operationen
• Initialisierung der Struktur
• Einfügen eines Auftrags (nach der Rangnummer)
• Entfernen -(bearbeiten)- eines Auftrags
Zudem:
• Inspektion des nächsten Auftrags
• Überprüfung der PWS: voll? leer?
• Drucken der Kollektion
Abstrakt formulierte Operationen: wenn man
ihre Signatur kennt, kann man eine solche
Prioritätswarteschlange benutzen.
29.01.2001
4
Vorl “EINI-I"
Kap 11: Prioritätswarteschlange
Realisierung über Feld
• Realisierungsmöglichkeit 1:
• geordnetes Feld, so daß
– einer der Aufträge mit der kleinsten Rangnummer am
Anfang steht;
– merke mir die Anzahl der aktuellen Aufträge.
29.01.2001
5
Vorl “EINI-I"
Kap 11: Prioritätswarteschlange
Realisierung über Feld
• Realisierung der Operationen:
– Initialisierung der Struktur: unmittelbar klar
– Einfügen eines Auftrags:
• Sortiere den Auftrag entsprechend der Ordnung in das Feld
ein
– Entfernen eines Auftrags:
• Entferne den (ersten) Auftrag, schiebe den Rest zusammen
– Inspektion des nächsten Auftrags:
• Betrachte das erste Element
– Überprüfung: voll? leer? unmittelbar klar
– Drucken der Kollektion: unmittelbar klar.
29.01.2001
6
Vorl “EINI-I"
Kap 11: Prioritätswarteschlange
Laufzeitanalyse
• Sieht doch ganz gut aus. Wo ist das Problem?
• Das Problem liegt in der Laufzeit, d.h. der
Anzahl der Operationen:
– Kosten der Operationen bei n Elementen:
• Einfügen eines Auftrags:
– Sortiere den Auftrag entsprechend der Ordnung in das
Feld ein (n Operationen)
• Entfernung eines Auftrags:
– Entferne den Auftrag, schiebe den Rest zusammen (n
Operationen)
• Argumentation bei Implementation durch
verkettete Listen: analog für das Einfügen
29.01.2001
7
Vorl “EINI-I"
Kap 11: Prioritätswarteschlange
Genauere Analyse
• Beobachtungen:
– Ich möchte stets nur Zugriff auf das kleinste Element
haben
– Die Sortierung befaßt sich jedoch mit allen
Elementen des Feldes
• Konsequenz:
– Versuche, das kleinste Element stets parat zu haben,
ohne alle Elemente zu sortieren.
• Suche in einer unsortierten Kollektion:
– ebenfalls n Operationen im schlechtesten Fall!
• --> Andere Datenstruktur: Heap
29.01.2001
8

Kapitel 11 - Prioritätswarteschlangen