Advanced DSA — Coding Interview Prep

Heaps

Why does your computer always know exactly which task is the absolute most urgent, without sorting the entire list first? Sorting everything is way too slow when things change every millisecond. Instead, computers use a clever shortcut called a heap.

A heap is a binary tree, but with two strict rules. First, it must be complete, meaning we fill every level from left to right with no gaps. This perfect shape keeps the tree incredibly compact.

The second rule is the heap property. In a min-heap, every parent node must be smaller than or equal to its children. This guarantees that the absolute smallest value is always sitting right at the very top.

But here is the beautiful part: we don't actually build trees with complex pointers in memory. Because the tree is complete, we can pack it into a simple, flat array. A node at index i has its children at two times i plus one, and two times i plus two.

When we insert a new element, we place it at the very end of our array to keep the tree complete. Then, if it violates the heap property, we bubble it up by swapping it with its parent until it finds its rightful place.

And that is the secret. By keeping the tree balanced and only swapping along a single path, heaps let us find the minimum in instant time, and add or remove elements in logarithmic time. It is the ultimate engine behind priority queues.