01 · Problem
What is it for?
Efficient prioritized removal depends on the heap invariant and an exact element count.
02 · Mental model
How should you think about it?
Store a complete binary tree in an array. Parent and child indexes are arithmetic, while swaps restore order.
Drains array and injected MongoDB-backed heaps in comparator order. Persistent operations require explicit initialization and one writer. Atomic multi-client MongoDB transactions remain outside the baseline.
03 · Control flow
What happens in which order?
- Append a value at the end.
- Bubble it toward its parent while smaller.
- Remove the root and replace it with the last item.
- Bubble the replacement down.
- Stop when no child violates ordering.
04 · Building blocks
The important contracts
ConcretePriorityQueue / MemoryPriorityQueueOwn an array-backed minimum heap.enqueue / dequeue / heapSortInsert, remove and drain in comparator order.MongoDBPriorityQueue.initDB / destroyConnect explicitly or inject a collection, then close explicitly.05 · Build it yourself
Implement a small core
Start with this small independent implementation, then use the steps below to make its contract explicit.
- Append a value at the end.
- Bubble it toward its parent while smaller.
- Remove the root and replace it with the last item.
- Bubble the replacement down.
- Stop when no child violates ordering.
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 · Verify
What should you test?
- Drain duplicates and random insertion orders into sorted output.
- Verify length reaches zero.
- Test an injected Mongo collection without opening a database during construction.
Try it yourself
Turn the first verification claim into a failing test, implement the smallest fix, then add a boundary case.
Drain duplicates and random insertion orders into sorted output.
Compare your approach
Your check should fail when the stated invariant is deliberately broken, and pass again after the fix. Keep setup deterministic and assert an observable result.
07 · Limits
Trade-offs and failure modes
- Async comparators make concurrent mutations unsafe without serialization.
- Persistent swaps are not automatically atomic.
- Length, capacity and last index are different quantities.
Persistent operations require explicit initialization and one writer. Atomic multi-client MongoDB transactions remain outside the baseline.
08 · Keep exploring
Source code and related ideas
yarn tsx packages/priority-queue/examples/basic.ts