Heap / Priority Queue

A pile where the smallest item is always on top, and adding or removing stays fast.

The idea (a hospital waiting room)

In an emergency room the most urgent patient is seen first, no matter who arrived first. A priority queue does that. A min-heap is a clever way to build one: a tree where every parent is smaller than or equal to its children. So the smallest value always sits at the very top (the root), and you can grab it instantly.

The trick is that the tree is stored in a plain array, with no pointers. For the item at index i: its children are at 2i+1 and 2i+2, and its parent is at (i-1)/2. The two views below are the same data.

Watch it work

Allowed: push N, pop, heapify N N N ... (heapify replaces the heap with that array). At most 20 operations and 15 items.

Try it

Common mistakes

Complexity, in plain English: reading the smallest is instant (O(1)). Push and pop move along one root-to-leaf path, so they take about log₂(n) steps (O(log n)): 1,000,000 items need only about 20 swaps. Heapify of a whole array takes only O(n).