01 · Problem
Wofür braucht man das?
Eine FIFO-Queue reicht nicht, wenn Dringlichkeit und stabile Reihenfolge bestimmen sollen, welcher Job als Nächstes läuft.
02 · Denkmodell
Das mentale Modell
Ein binärer Heap hält am Root das beste Element. push repariert den Pfad nach oben, pop ersetzt den Root durch das letzte Element und repariert nach unten.
Entnimmt Werte aus Array- und injizierten MongoDB-Heaps in Comparator-Reihenfolge. Persistenz erfordert explizite Initialisierung und einen Writer. Atomare MongoDB-Transaktionen für mehrere Clients liegen außerhalb des Basiskerns.
03 · Kontrollfluss
Was passiert in welcher Reihenfolge?
- Element am echten Arrayende einfügen und gegen Eltern vergleichen.
- Solange es höher priorisiert ist, mit dem Elternknoten tauschen.
- Beim pop Root sichern, letztes Element entfernen und gegebenenfalls nach vorne setzen.
- Mit dem besseren Kind tauschen, bis die Heap-Invariante wieder gilt.
- Gleiche Priorität über eine monotone Sequenz stabil ordnen.
04 · Bauteile
Die entscheidenden Verträge
ConcretePriorityQueue / MemoryPriorityQueueVerwaltet einen Array-basierten Min-Heap.enqueue / dequeue / heapSortFügt ein, entfernt und leert in Comparator-Reihenfolge.MongoDBPriorityQueue.initDB / destroyVerbindet explizit oder injiziert eine Collection und schließt explizit.05 · Selbst bauen
Selbst implementieren
Baue zuerst einen korrekten synchronen In-Memory-Heap. Persistenz ist ein anderes Datenmodell und sollte atomare Datenbankoperationen nutzen.
- Nutze ausschließlich items.length als Elementanzahl.
- Implementiere bubble-up und bubble-down mit einem synchronen Comparator.
- Für persistente Jobs speichere priority plus sequence und claim'e atomar per sortiertem findOneAndUpdate.
class Heap<T> {
private items: T[] = [];
constructor(private compare: (a: T, b: T) => number) {}
push(value: T) {
this.items.push(value);
for (let i = this.items.length - 1; i > 0;) {
const parent = Math.floor((i - 1) / 2);
if (this.compare(this.items[i], this.items[parent]) >= 0) break;
[this.items[i], this.items[parent]] = [this.items[parent], this.items[i]];
i = parent;
}
}
}06 · Verifizieren
Was solltest du testen?
- Zufällige push/pop-Sequenzen liefern dieselbe Reihenfolge wie ein vollständig sortiertes Referenzarray.
- Leere, ein-elementige und duplikate Queues erhalten Länge und Heap-Invariante.
- Gleiche Prioritäten bleiben über sequence stabil; konkurrierende Persistenz-Claims liefern jeden Job einmal.
Selbst ausprobieren
Formuliere die erste Prüfaussage als fehlschlagenden Test, implementiere die kleinste Korrektur und ergänze einen Grenzfall.
Zufällige push/pop-Sequenzen liefern dieselbe Reihenfolge wie ein vollständig sortiertes Referenzarray.
Ansatz vergleichen
Dein Test sollte beim gezielten Verletzen der Invariante fehlschlagen und nach der Korrektur wieder bestehen. Halte den Aufbau deterministisch und prüfe ein beobachtbares Ergebnis.
07 · Grenzen
Kompromisse und Stolperfallen
- Ein Heap bietet O(log n) push/pop, aber keine schnelle Suche oder Entfernung beliebiger Elemente.
- Async-Comparatoren machen jede Reparatur langsam und race-anfällig.
- Ein Heap über viele Mongo-Dokumente ist kein atomarer verteilter Heap; sortierte Job-Claims passen besser zur Datenbank.
Persistenz erfordert explizite Initialisierung und einen Writer. Atomare MongoDB-Transaktionen für mehrere Clients liegen außerhalb des Basiskerns.
08 · Weiterdenken
Quellcode und verwandte Ideen
yarn tsx packages/priority-queue/examples/basic.ts