Heaps

Why heaps exist (motivation)

Often you don’t need a fully sorted list—you just need to repeatedly answer questions like:

• •“What’s the smallest item right now?”
• •“Give me the next highest priority task.”
• •“I inserted something new—how does that affect the next thing I should process?”

A heap is designed for exactly this pattern: frequent insert and frequent remove the min/max.

Definition (binary heap)

A binary heap is a binary tree with two constraints:

1. 1)Shape constraint (complete binary tree):

• •Every level is completely filled except possibly the last.
• •The last level is filled left-to-right.

2. 2)Heap-order property (local ordering):

• •Min-heap: every parent is ≤ each of its children.
• •Max-heap: every parent is ≥ each of its children.

This ordering is local, not global. In a min-heap, the root is the minimum element, but the rest of the tree is not necessarily sorted.

What you get “for free”

From the heap-order property:

• •In a min-heap, the minimum element is at the root.
• •In a max-heap, the maximum element is at the root.

So:

• •peek-min / peek-max is O(1).

What you don’t get

A heap does not support:

• •Fast search for an arbitrary value (still O(n) in general)
• •Sorted iteration without extra work (if you repeatedly remove-min you will get sorted order, but that costs O(n log n) total)

Difficulty calibration note

This node is Difficulty 2–3/5. Core heap operations are approachable (2/5), but using heaps inside graph algorithms (like Dijkstra) introduces subtleties (often closer to 3/5). This lesson keeps Dijkstra-related details optional/advanced.

Why the shape matters

The complete-tree shape makes heaps efficient because the tree height stays small.

If $n$ is the number of nodes, the height is $O(\log n)$ (more precisely, about $\lfloor \log_2 n \rfloor$).

That’s the key reason sift-up and sift-down are fast: they only walk a single path from a leaf to the root (or vice versa), and that path length is at most the height.

Array representation (0-based indexing)

A binary heap is almost always stored in an array rather than explicit node pointers.

Because the tree is complete, nodes can be laid out level-by-level (breadth-first order) with no gaps.

For index $i$ (0-based), the relationships are:

• •parent(i) = ⌊(i − 1) / 2⌋
• •left(i) = 2i + 1
• •right(i) = 2i + 2

These formulas come from how a complete binary tree packs into an array.

Example: mapping indices to a tree

Suppose the heap array is:

Index: 0 1 2 3 4 5 6

Value: 2 5 3 9 7 4 8

Tree structure (conceptually):

• •Index 0 is the root (2)
• •Children of 0 are indices 1 and 2 (5 and 3)
• •Children of 1 are indices 3 and 4 (9 and 7)
• •Children of 2 are indices 5 and 6 (4 and 8)

Quick complexity table

Heaps sit in the “sweet spot”: they keep just enough structure to make min/max cheap, without making insertion too expensive.

Why operations are “local repairs”

The heap property is local (parent vs. children). That means when you modify the heap in a controlled way, you typically break the property in only one area.

Heaps exploit this: after an insert or remove, you repair the heap by swapping along one path.

There are two fundamental repair operations:

• •sift-up (a.k.a. bubble-up, percolate-up)
• •sift-down (a.k.a. heapify-down, percolate-down)

We’ll describe everything using a min-heap. For a max-heap, flip the comparisons.

Insert(x): append then sift-up

Why append?

To preserve the complete-tree shape, you must add the new node at the next available spot: the end of the array.

This may violate heap order (the new value might be smaller than its parent), but the violation is on the path from that new leaf to the root.

Sift-up logic

Let i be the index of the newly appended item.

While i > 0 and heap[i] < heap[parent(i)]:

• •swap heap[i] with heap[parent(i)]
• •update i = parent(i)

Each swap moves the element one level closer to its correct place.

Cost

Each iteration moves up one level. There are at most O(log n) levels.

So insert is O(log n).

removeMin(): move last to root then sift-down

Why move the last element to the root?

We need to remove the root (the minimum), but if we simply delete it, we would create a hole and break the complete-tree shape.

Instead:

1. 1)Save heap[0] as the answer.
2. 2)Move the last element into heap[0].
3. 3)Pop the last slot.

Now the shape is preserved, but heap order may be violated at the root (the moved element might be too large compared to children).

Sift-down logic

Starting at i = 0:

• •Compare heap[i] with its children.
• •Swap heap[i] with the smaller child if that child is smaller than heap[i].
• •Continue at the child index.

Stop when:

• •i has no children, or
• •heap[i] ≤ both children.

Cost

Each swap moves down one level, and there are O(log n) levels.

So removeMin is O(log n).

Peek

peekMin() just returns heap[0] (if non-empty), so O(1).

Build-heap (bonus)

If you’re given an arbitrary array and want to turn it into a heap:

• •Naive approach: insert each item one-by-one → O(n log n).
• •Bottom-up heapify: run sift-down from the last parent down to root → O(n).

The O(n) result can feel surprising. Intuition: most nodes are near the bottom, and sifting down from them is very cheap.

A standard bottom-up approach for an array of length n:

• •Start i = parent(n − 1)
• •While i ≥ 0: siftDown(i)

This is the core of heapsort as well.

Priority queue = heap + interface

A priority queue is an abstract data type (ADT) with operations like:

• •push(item, priority)
• •peek() (returns min or max)
• •pop() (removes and returns min or max)

A binary heap is the most common implementation.

Typical real-world uses

• •Scheduling tasks by urgency
• •Event simulation (next event time)
• •Streaming: keep top-k elements (often using a size-k heap)
• •Graph algorithms: Dijkstra’s algorithm (min-priority queue)

Heapsort connection

If you:

1. 1)Build a max-heap
2. 2)Repeatedly removeMax and place it at the end

You get an in-place sorting algorithm with O(n log n) time and O(1) extra space (ignoring recursion).

Heapsort is not stable, but it has strong worst-case guarantees.

Advanced/Optional: Dijkstra and decrease-key

Dijkstra’s algorithm conceptually needs a priority queue that supports:

• •extract-min
• •decrease-key (lower the priority of an existing node)

A binary heap can support decrease-key efficiently if you can find the element’s index in the heap array (often by maintaining a map from node → heap index).

Common library behavior (important caveat)

Many standard libraries (e.g., Python’s heapq, Java’s PriorityQueue) do not provide a direct decrease-key operation.

Common workaround:

• •When a node’s distance decreases, push a new (better) entry anyway.
• •When popping, ignore stale entries that no longer match the best-known distance.

This keeps the code simple but changes the operational profile:

• •The heap may contain multiple entries per node.
• •Complexity can become closer to O((E + K) log (E + K)) where K is the number of extra pushes (often still acceptable in practice).

If you later unlock the Shortest Paths node, you’ll see how this affects correctness and runtime in detail.