Implementing a Task Heap Service in TypeScript
Imagine a task queue where you always want to run the shortest task first. A sorted array would work, but inserting into a sorted array is O(n). A min-hea...
29 Apr 2024
Imagine a task queue where you always want to run the shortest task first. A sorted array would work, but inserting into a sorted array is O(n). A min-heap gives you O(log n) insert and O(log n) extract-min. That's the difference between a system that scales and one that doesn't.
A heap is a binary tree stored as an array. The parent at index i has children at 2i + 1 and 2i + 2. In a min-heap, every parent is smaller than its children. The smallest element is always at the root.
The implementation
interface Task {
executionTime: number;
name: string;
}
class TaskHeapService {
private heap: Task[] = [];
insert(task: Task): void {
this.heap.push(task);
this.bubbleUp(this.heap.length - 1);
}
extractMin(): Task | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const last = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = last;
this.sinkDown(0);
}
return min;
}
peek(): Task | undefined {
return this.heap[0];
}
get size(): number {
return this.heap.length;
}
private bubbleUp(index: number): void {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex].executionTime <= this.heap[index].executionTime) break;
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
index = parentIndex;
}
}
private sinkDown(index: number): void {
const length = this.heap.length;
while (true) {
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < length && this.heap[left].executionTime < this.heap[smallest].executionTime) {
smallest = left;
}
if (right < length && this.heap[right].executionTime < this.heap[smallest].executionTime) {
smallest = right;
}
if (smallest === index) break;
[this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
index = smallest;
}
}
}Complexity
- Insert: O(log n) — bubble up at most the height of the tree.
- Extract min: O(log n) — sink down at most the height.
- Peek: O(1) — the min is always at index 0.
- Space: O(n) for n tasks.
Why not just sort?
Sorting the array after every insert costs O(n log n). A heap does the same job incrementally — each operation touches O(log n) elements. When tasks arrive continuously (like in a job scheduler or event loop), that difference compounds fast.
The trade-off: a heap only guarantees the min (or max) is at the top. It doesn't give you fully sorted order. If you need the top-k elements or just the next task to run, a heap is perfect. If you need everything sorted, you still need a full sort.