Binäre Priorisierung

Binäres Priorisieren oder Binäre Priorisierung ist ein Sortierverfahren, mit dem eine Menge zu erledigender Aufgaben priorisiert (oder allgemeiner: zu sortierenden Elemente sortiert) werden kann, indem wichtige Aufgaben im Laufe des Priorisier-Prozesses immer weiter nach oben priorisiert werden, während zurückgestellte Aufgaben nicht weiter priorisiert werden.

Im Gegensatz zu anderen binären Verfahren (z. B. der Binären Suche) geht man bei der Anwendung dieses Verfahrens davon aus, dass die zurückgestellten Aufgaben in einem späteren Prozess erneut priorisiert werden (müssen), aber deren Reihenfolge zum aktuellen Zeitpunkt nicht relevant ist. Dadurch wird eine schnellere Bearbeitung der als wichtiger eingestuften Aufgaben erreicht und der Aufwand des Sortierens aufgrund der nicht zu sortierenden Teilmenge der weniger wichtigen Aufgaben reduziert. In jeder Iteration wird der Aufwand um die aussortierten Elemente reduziert.

Voraussetzungen für die Anwendung

Bei der Anwendung der Binären Priorisierung wird vorausgesetzt, dass die zu priorisierenden Elemente in einem unsortierten Stapel (abstrakter: einer unsortierten Liste) vorliegen.

Algorithmus

Der Algorithmus der Binären Priorisierung läuft wie folgt ab:

Stufe 1

• Dem Stapel (bzw. der Liste) wird ein Element entnommen.
• Das Element (die Aufgabe) wird auf Priorität (Wichtigkeit) relativ zu den anderen Elementen analysiert.

Stufe 2

• Wird das Element als wichtig beurteilt, wird es auf einen neuen Stapel (in eine neue Liste) wichtiger Elemente sortiert; wird es stattdessen als unwichtig angesehen, wird es auf einen anderen Stapel (in eine andere Liste) unwichtiger Elemente sortiert. Dies wird im ersten Durchlauf solange wiederholt, bis alle Elemente beurteilt wurden und in zwei neuen Stapeln (bzw. Listen) vorliegen.

Stufe 3

• Die beiden Stapel (Listen) werden wieder vereinigt, indem der Stapel der wichtigen Elemente auf den der als unwichtig angesehenen Elemente gelegt wird. Dabei merkt man sich das letzte Element der Liste der als wichtig eingestuften Elemente (Trenner).

Stufe 4

• Der Algorithmus wird anschließend in einer weiteren Iteration auf den neu entstandenen (vereinigten) Stapel bis zu dem Element angewandt, bis das gemerkte Trenner-Element bearbeitet wurde.
• Wurde im letzten Schritt nur ein Element bearbeitet, ist der Algorithmus abgeschlossen. Die als am wichtigsten eingestuften Elemente liegen dem Stapel obenauf, während die untersten Elemente als unwichtig eingestuft, in sich aber nicht sortiert wurden.

Anwendung

Ein Beispiel für die Anwendung des Binären Sortierens ist folgendes Szenario:

Dem Bearbeiter eines Postkorbs liegt ein Stapel zu beantwortender Briefe oder eine große Menge eingegangener E-Mails vor, die nicht in der Reihenfolge des Eingangs, sondern nach Wichtigkeit sortiert bearbeitet werden sollen (vergleiche Postkorb-Fallstudie). In der Zeit, in der der Bearbeiter die eher unwichtigen E-Mails nach Wichtigkeit sortiert, könnte er schon mit dem Bearbeiten oder Weiterleiten der wichtigen begonnen haben und die eher unwichtigen in einem zweiten Durchlauf sortieren.