Zum Inhalt
wannacode

Prioritätswarteschlange

Kurz gesagt: Eine Prioritätswarteschlange gibt immer das wichtigste Element zurück, zum Beispiel die dringendste Bestellung; auf einem Heap sind Einfügen und Entnehmen O(log n), und JavaScript hat keine eingebaute, also schreibst du eine kleine Klasse.

Problem

Wer zuerst dran ist

Der Lieferdispatcher verteilt Bestellungen an die Kuriere. Jede Bestellung hat eine Frist: in wie vielen Minuten sie vor der Tür des Kunden sein muss. Ein freier Kurier bekommt immer die dringendste Bestellung.

Bestellungen kommen ständig herein. An einem Freitagabend in einer Großstadt warten 10.000 auf einmal, und 100.000 laufen an einem Tag durch.

Die erste Lösung ist eine nach Frist sortierte Liste. Bei jeder neuen Bestellung fügst du sie ein und sortierst die Liste neu. Sortieren kostet O(n log n) (siehe Mergesort), und das für jede Bestellung. Selbst die klügste Sortierung, die merkt, dass die Liste fast sortiert ist, muss sie mindestens durchlaufen: n Schritte bei jeder neuen Bestellung.

Und der Kurier braucht nicht die ganze Reihenfolge der Liste. Nur die erste.

Die Idee

Eine Warteschlange, die nur weiß, wer der Erste ist

Eine Struktur mit zwei Aktionen: eine Bestellung einfügen und die dringendste entnehmen. Das ist eine Prioritätswarteschlange. Sie verspricht keine Reihenfolge für alle, nur wer der Erste ist.

Genau das macht der Heap aus der Lektion zum Heapsort. Hier ist er umgedreht: ein Min-Heap, in dem jeder Elternknoten höchstens so groß ist wie seine Kinder. Dann steht die früheste Frist immer an Index 0.

  • Entnehmen kennst du schon vom Heapsort. Die Spitze geht, das letzte Element nimmt ihren Platz ein und sinkt nach unten. Der Unterschied: Es sinkt zum dringenderen Kind.
  • Einfügen ist das Neue: Aufsteigen. Die neue Bestellung kommt ans Ende des Arrays. Dann wird sie mit ihrem Elternknoten an Index (i - 1) / 2 verglichen. Ist sie dringender, tauschen sie die Plätze, und sie steigt weiter. Sie bleibt stehen, wenn der Elternknoten dringender ist oder wenn sie oben ankommt.

Sieh es dir an

Aufsteigen und Absinken

Einfügen: ans Ende, dann nach oben.

push(order) {
  this.#items.push(order);
  let i = this.#items.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (!this.#less(i, parent)) return;
    this.#swap(i, parent);
    i = parent;
  }
}

Entnehmen: Die Spitze geht, das letzte Element nimmt ihren Platz ein und sinkt.

poll() {
  const items = this.#items;
  const top = items[0];
  items[0] = items[items.length - 1];
  items.pop();
  if (items.length > 0) this.#siftDown(0);
  return top;
}


#siftDown(i) {
  const n = this.#items.length;
  while (true) {
    let low = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && this.#less(left, low)) {
      low = left;
    }
    if (right < n && this.#less(right, low)) {
      low = right;
    }
    if (low === i) return;
    this.#swap(i, low);
    i = low;
  }
}
#items und #siftDown sind privat: Von außen siehst du nur push, poll und size.

Sechs Bestellungen warten. Eine neue mit 18 Minuten kommt herein, und der Kurier nimmt die dringendste:

const waiting = [
  { id: "A-101", deadline: 10 },
  { id: "A-102", deadline: 15 },
  { id: "A-103", deadline: 30 },
  { id: "A-104", deadline: 20 },
  { id: "A-105", deadline: 25 },
  { id: "A-106", deadline: 40 },
];
const queue = new DeadlineQueue();
for (const o of waiting) queue.push(o);
console.log(`Heap: ${queue.deadlines()}`);
queue.push({ id: "A-107", deadline: 18 });
console.log(`Nach A-107: ${queue.deadlines()}`);
const next = queue.poll();
console.log(`Der Kurier nimmt ${next.id} (${next.deadline} Min.)`);
console.log(`Übrig: ${queue.deadlines()}`);
Ausgabe
Heap: [10, 15, 30, 20, 25, 40]
Nach A-107: [10, 15, 18, 20, 25, 40, 30]
Der Kurier nimmt A-101 (10 Min.)
Übrig: [15, 20, 18, 30, 25, 40]

class DeadlineQueue {
  #items = [];


  push(order) {
    this.#items.push(order);
    let i = this.#items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.#less(i, parent)) return;
      this.#swap(i, parent);
      i = parent;
    }
  }


  poll() {
    const items = this.#items;
    const top = items[0];
    items[0] = items[items.length - 1];
    items.pop();
    if (items.length > 0) this.#siftDown(0);
    return top;
  }


  #siftDown(i) {
    const n = this.#items.length;
    while (true) {
      let low = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.#less(left, low)) {
        low = left;
      }
      if (right < n && this.#less(right, low)) {
        low = right;
      }
      if (low === i) return;
      this.#swap(i, low);
      i = low;
    }
  }


  #less(i, j) {
    const items = this.#items;
    return items[i].deadline < items[j].deadline;
  }


  #swap(i, j) {
    const items = this.#items;
    [items[i], items[j]] = [items[j], items[i]];
  }


  get size() {
    return this.#items.length;
  }


  deadlines() {
    const all = this.#items.map((o) => o.deadline);
    return `[${all.join(", ")}]`;
  }
}
Schritt für Schritt, in Worten
  1. Sechs wartende Bestellungen, die Fristen sind in Minuten. Ein Min-Heap: Jeder Elternknoten ist höchstens so groß wie seine Kinder, deshalb liegt die dringendste, 10, oben.
  2. push: Eine neue Bestellung mit 18 Minuten kommt ans Ende des Arrays, Index 6. Im Baum ist sie ein Kind von 30.
  3. Aufsteigen: Der Elternknoten von 6 ist (6 - 1) / 2 = 2. 18 ist dringender als 30, also tauschen sie.
  4. Der Elternknoten von 2 ist 0, mit 10 Minuten. 10 ist dringender als 18: Die Bestellung bleibt stehen. Ein Tausch, höchstens einer pro Ebene.
  5. poll: Der Kurier nimmt die Spitze, die Bestellung mit 10 Minuten. An Index 0 bleibt eine Lücke.
  6. Das letzte Element, 30, springt nach oben und das Array schrumpft auf sechs. Jetzt setzt #siftDown es an seinen Platz.
  7. Absinken, wie beim Heapsort, aber zum dringenderen Kind: 30 gegen 15 und 18 tauscht mit 15, dann gegen 20 und 25 tauscht mit 20.
  8. Index 3 hat keine Kinder: fertig. Oben liegt 15, die nächstdringende. Beide Bewegungen kosten O(log n): die Höhe des Baums.

Das Array ist nicht sortiert: 18 steht vor 20. Sortiert ist nur, was zählt: Die früheste Frist liegt oben.

Probier es aus

Sag die Ausgabe voraus

Fünf Bestellungen kommen in eine leere Warteschlange. Was steht danach im Array?

const queue = new DeadlineQueue();
queue.push({ id: "B-1", deadline: 40 });
queue.push({ id: "B-2", deadline: 25 });
queue.push({ id: "B-3", deadline: 30 });
queue.push({ id: "B-4", deadline: 10 });
queue.push({ id: "B-5", deadline: 35 });
console.log(queue.deadlines());
Antwort

Probier es aus

Ergänze

Beim Aufsteigen wird das Element an Index i mit seinem Elternknoten verglichen. Wo liegt der Elternknoten?

const parent = ;

Die Idee

Was es kostet

  • Einfügen: höchstens ein Vergleich pro Ebene. Ein Baum mit n Elementen hat etwa log₂ n Ebenen: O(log n).
  • Entnehmen: zwei Vergleiche pro Ebene beim Absinken: ebenfalls O(log n).
  • Wer der Erste ist: Die Spitze liegt an Index 0, ohne einen einzigen Vergleich: O(1).

Lass den Dispatcher mit beiden Versionen laufen. Die Bestellungen kommen nacheinander, nach jeder zweiten nimmt ein Kurier die dringendste, und am Ende nehmen die Kuriere den Rest. Gezählt werden die Vergleiche zwischen zwei Fristen:

  • Sortierte Liste: nach jeder Bestellung neu sortieren O(n²)
  • Min-Heap: nach oben und nach unten sieben O(n log n)
Algorithmusn = 10n = 1.000n = 10.000n = 100.000
Sortierte Liste: nach jeder Bestellung neu sortieren1163.4306.250.042≈ 625.004.200
Min-Heap: nach oben und nach unten sieben2817.397256.8073.386.161
Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.
class DeadlineQueue {
  #items = [];


  push(order) {
    this.#items.push(order);
    let i = this.#items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.#less(i, parent)) return;
      this.#swap(i, parent);
      i = parent;
    }
  }


  poll() {
    const items = this.#items;
    const top = items[0];
    items[0] = items[items.length - 1];
    items.pop();
    if (items.length > 0) this.#siftDown(0);
    return top;
  }


  #siftDown(i) {
    const n = this.#items.length;
    while (true) {
      let low = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.#less(left, low)) {
        low = left;
      }
      if (right < n && this.#less(right, low)) {
        low = right;
      }
      if (low === i) return;
      this.#swap(i, low);
      i = low;
    }
  }


  #less(i, j) {
    const items = this.#items;
    return items[i].deadline < items[j].deadline;
  }


  #swap(i, j) {
    const items = this.#items;
    [items[i], items[j]] = [items[j], items[i]];
  }


  get size() {
    return this.#items.length;
  }


  deadlines() {
    const all = this.#items.map((o) => o.deadline);
    return `[${all.join(", ")}]`;
  }
}

Bei 10 Bestellungen macht die sortierte Liste 11 Vergleiche und der Heap 28: Bei wenigen Bestellungen ist die Liste völlig in Ordnung. Bei 10.000 sind es 6.250.042 gegen 256.807. Bei 100.000 macht der Heap 3.386.161, die Liste etwa 625 Millionen. Das lässt Bench nicht laufen, es schätzt es aus der Kurve.

Die sortierte Liste in Bench ist im besten Fall: Die neue Bestellung rutscht nur an ihren Platz, nichts anderes wird sortiert. Es bleibt trotzdem O(n) pro Bestellung, weil sie im Schnitt die halbe Liste durchläuft. Der Heap ist O(log n) pro Bestellung.

Genauer, für Neugierige

Welche Sortierung merkt, dass die Liste fast sortiert ist? TimSort, das sort in Python, List.sort und Collections.sort in Java und Array.prototype.sort in JavaScript verwenden (siehe die eingebaute Sortierung). Es findet den sortierten Teil mit etwa n Vergleichen und setzt das neue Element dort ein: O(n) pro Bestellung. Bench zählt eine noch billigere Variante, das Rutschen vom Ende her, und es kommt trotzdem O(n) heraus. C# List.Sort ist Introsort und sucht keine sortierten Teile: Bei jeder Bestellung macht es etwa n log n Vergleiche, noch mehr.

Warum ist das Aufsteigen auch in der Praxis schnell? Eine neue Bestellung liegt meist irgendwo in der Mitte der Dringlichkeit. Die Hälfte der Elemente eines Heaps sind Blätter, ein Viertel liegt direkt darüber, und so weiter. Im Schnitt bleibt eine zufällige Bestellung also nach ein, zwei Ebenen stehen. Der schlimmste Fall (die neue ist die dringendste von allen) sind trotzdem nur log₂ n.

Probier es aus

Finde den Fehler

Ein Kollege hat das Absinken geschrieben, aber die Kuriere fahren manchmal mit einer späteren Bestellung vor einer früheren los:

#siftDown(i) {
  const n = this.#items.length;
  while (true) {
    let low = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && this.#less(left, low)) {
      low = left;
    }
    if (right < n && this.#less(right, i)) {
      low = right;
    }
    if (low === i) return;
    this.#swap(i, low);
    i = low;
  }
}
const queue = new DeadlineQueue();
queue.push({ id: "C-1", deadline: 5 });
queue.push({ id: "C-2", deadline: 10 });
queue.push({ id: "C-3", deadline: 20 });
queue.push({ id: "C-4", deadline: 30 });
queue.push({ id: "C-5", deadline: 40 });
queue.push({ id: "C-6", deadline: 50 });
const taken = [];
while (queue.size > 0) taken.push(queue.poll().deadline);
console.log(`[${taken.join(", ")}]`);
Ausgabe
[5, 20, 10, 30, 40, 50]

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Sieh es dir an

Die fertigen Warteschlangen jeder Sprache

In einem Projekt schreibst du keinen Heap selbst. Fast jede Sprache hat eine Prioritätswarteschlange, und jede hat ihre Eigenheit.

JavaScript hat keine eingebaute Prioritätswarteschlange. Wir nehmen also unsere DeadlineQueue von oben. In einem Projekt nimmst du ein fertiges Paket von npm oder eine kurze Klasse wie diese.

const queue = new DeadlineQueue();
queue.push({ id: "A-101", deadline: 30 });
queue.push({ id: "A-102", deadline: 10 });
queue.push({ id: "A-103", deadline: 20 });
queue.push({ id: "A-104", deadline: 25 });
console.log(`Innen: ${queue.deadlines()}`);
while (queue.size > 0) {
  const o = queue.poll();
  console.log(`${o.id} (${o.deadline} Min.)`);
}
Ausgabe
Innen: [10, 25, 20, 30]
A-102 (10 Min.)
A-103 (20 Min.)
A-104 (25 Min.)
A-101 (30 Min.)
Genauer, für Neugierige

Keine dieser Warteschlangen ist stabil: Zwei Bestellungen mit derselben Frist können in beliebiger Reihenfolge herauskommen (siehe Stabilität). Wenn die Reihenfolge des Eintreffens wichtig ist, füge eine laufende Nummer hinzu, wie oben in Python.

Die Frist einer Bestellung, die schon wartet, lässt sich in keiner der drei ändern. remove in Java sucht das Element linear: O(n). Die übliche Lösung ist, die Bestellung mit der neuen Frist noch einmal einzufügen und die alte Kopie zu überspringen, wenn sie herauskommt. So arbeitet auch Dijkstra im kommenden Modul über Graphen (algo-graphs).

Wie es in den anderen Sprachen ist: Java hat PriorityQueue, C# PriorityQueue<TElement, TPriority> (seit .NET 6), Python heapq (Funktionen auf einer Liste), und JavaScript hat keine eingebaute Prioritätswarteschlange.

Sieh es dir an

Zwei weitere Aufgaben für einen Heap

Die obersten k. Welche 10 von einer Million Produkten verkaufen sich am besten? Ein Min-Heap, der nie mehr als 10 Elemente enthält: Jedes neue wird mit der Spitze verglichen. Das steht in der Lektion zum Heap, mit einem Bench dazu.

k sortierte Listen zusammenführen. Drei Lager schicken ihre Bestellungen nach Frist sortiert. Du brauchst eine gemeinsame Route, wieder nach Frist. Der Heap enthält nur den Kopf jeder Liste. Du nimmst den frühesten, und an seine Stelle setzt du den nächsten aus demselben Lager:

In JavaScript ist das wieder unsere DeadlineQueue: Sie vergleicht nur deadline, also nimmt sie auch Objekte an, die sich das Lager und die Position merken.
const lists = [[5, 20, 45], [10, 15, 50], [12, 30]];
const names = ["Nord", "Süd", "Mitte"];
const heads = new DeadlineQueue();
lists.forEach((list, k) => heads.push({ deadline: list[0], list: k, index: 0 }));
const route = [];
while (heads.size > 0) {
  const h = heads.poll();
  route.push(`${h.deadline} ${names[h.list]}`);
  const next = h.index + 1;
  if (next < lists[h.list].length) {
    heads.push({ deadline: lists[h.list][next], list: h.list, index: next });
  }
}
console.log(`Route: ${route.join(", ")}`);
Ausgabe
Route: 5 Nord, 10 Süd, 12 Mitte, 15 Süd, 20 Nord, 30 Mitte, 45 Nord, 50 Süd

Der Heap enthält nie mehr als k Elemente (hier 3). N Bestellungen kosten also O(N log k), nicht O(N log N) wie beim Sortieren von allem. So werden auch die sortierten Teile einer Datei zusammengeführt, die nicht in den Speicher passt.

Genauer, für Neugierige
Python hat eine fertige Zusammenführung: heapq.merge. In Java, C# und JavaScript schreibst du sie wie hier.

Mergesort führt auch sortierte Teile zusammen, aber zwei auf einmal (Mergesort). Ein Heap führt k auf einmal zusammen.

Übung

Eine faire Warteschlange

Löse die Aufgabe in deinem Editor.

Gleiche Frist, die frühere zuerst. Baue eine Warteschlange FairQueue, in der bei gleicher Frist die Bestellung zuerst herauskommt, die früher gekommen ist. Speichere zu jeder Bestellung eine laufende Nummer und vergleiche zuerst nach Frist, dann nach Nummer. Lass sie mit den Bestellungen A-1 (30), A-2 (20), A-3 (30), A-4 (20), A-5 (10), A-6 (20) in dieser Reihenfolge laufen:

Ausgabe
Reihenfolge: A-5, A-2, A-4, A-6, A-1, A-3

Weitere Aufgaben

  • Max-Heap. Dreh den Vergleich um und baue eine Warteschlange, die zuerst die teuerste Bestellung liefert.
  • Vergleiche zählen. Füge dem Aufsteigen und dem Absinken einen Zähler hinzu und lass 1000 zufällige Bestellungen laufen. Wie viele Vergleiche fallen auf eine Bestellung?
  • Die obersten drei. Wie bekommst du die drei dringendsten Bestellungen, ohne die anderen aus der Warteschlange zu nehmen?

Test

Teste dich

1. Was verspricht eine Prioritätswarteschlange?
2. Eine neue Bestellung kommt in einen Heap mit 1.000.000 Bestellungen. Wie viele Vergleiche macht das Aufsteigen höchstens?
3. In Python speicherst du Bestellungen als (Frist, dict) in heapq. Zwei Bestellungen haben dieselbe Frist. Was passiert?
4. Drei Lager schicken nach Frist sortierte Listen, insgesamt N Bestellungen. Wie führst du sie zu einer Route zusammen?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·