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.
Abstract-, Concrete-, Memory- und MongoDB-Backends teilen einen Async-Heapalgorithmus. Längen- und Löschlogik korrumpieren bereits die In-Memory-Queues; Mongo-Initialisierung und Mehrschritt-Swaps sind nicht atomar.
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
Array-Backend, das entfernte Slots aktuell auf null setzt statt die Länge zu verkürzen.
MemoryPriorityQueue
Eigenes Längenmodell, das Index, Kapazität und Elementanzahl verwechselt.
MongoDBPriorityQueue
Persistenter Heap mit nicht atomaren Swaps und nicht abgewarteter Initialisierung.
enqueue / dequeue / peek / heapSort
Gemeinsame abstrakte Queue-Operationen.
05 · Build it yourself
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 du testen solltest
- 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.
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.
Länge, letzter Index und Kapazität sind drei verschiedene Begriffe. Der vorhandene Code vermischt sie und verletzt dadurch die zentrale Heap-Invariante.
08 · Weiterdenken