Unit 3 · Lesson 520 minAcademic review pending

The emergency room, not the ticket counter

Unit I's queue serves whoever arrived first. A heap serves whoever matters most right now — the most critical patient, not the one who has waited longest.

Choose explanation

After this lesson

You should be able to

State the heap property for a max-heap and a min-heap.
Insert into a heap using bubble-up.
Extract the root using bubble-down.

Try it before you read

Try it live

heap.c0 node(s)

Empty heap — insert a value to begin.

Not first-come-first-served — most-urgent-first

A hospital emergency room does not serve patients in arrival order — that is Unit I's queue, and it would be dangerous here. It serves whoever is most critical right now, even if they just walked in and others have been waiting for hours. A heap is the data structure for exactly this: always give me the most extreme value, cheaply, no matter what order things arrived in.

This is called a priority queue when described by behaviour rather than implementation — 'give me the highest priority item next' — and a binary heap is the standard way to build one.

The heap property, and the shape rule

A max-heap requires every node to be at least as big as both its children — the most extreme value is therefore always the root, reachable in one step. A min-heap requires the opposite. Unlike Unit II's BST, there is no left-smaller-right-bigger rule between siblings — only parent versus child matters.

A heap must also stay a complete tree — every level full except possibly the last, which fills left to right with no gaps. That single shape rule is what makes Unit II Lesson 2's array representation, index i with children at 2i + 1 and 2i + 2, work perfectly here with no wasted space, unlike a general binary tree.

The array is the tree; no pointers needed

Array: [50, 30, 40, 10, 20]

Tree view:
             50
           /    \
         30      40
        /  \
      10    20

/* every parent >= both children — a valid max-heap */

Insert: bubble up

Add the new value at the very next open array slot — the shape rule says exactly where that is. That may break the heap property against its new parent, so swap the two and repeat the check one level up, one comparison at a time, until the value settles or reaches the root.

Because the array is a complete tree, this walk is never longer than the tree's height — for a heap of a million elements, about twenty swaps, at most.

Try it yourself

Using the max-heap below, insert 15, 60, 5, 45 in that order, predicting after each insertion whether it bubbles up and how far.

Need a hint?

A value only keeps bubbling up while it is bigger than its current parent.

Check the worked solution

15 becomes the root with nothing to compare against. 60 is bigger than the root, so it bubbles all the way up and becomes the new root. 5 is smaller than its parent, so it stays put with no swaps. 45 is bigger than its immediate parent but smaller than the root, so it bubbles up exactly one level and stops. Predicting the stopping point before the widget confirms it is the actual exercise.

Quick check

In a max-heap, why is the root guaranteed to be the largest value?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Binary Heaps

Maps to course outcomes CO1, CO4.