P-4.6 Heaps and Priority Ordering

What this is and why it exists

A heap answers exactly one question well: what is the smallest thing left.

It does not keep everything sorted, and that is precisely why it is cheaper than a structure that does. Asking for less is what makes it fast — a useful pattern to notice, because it recurs.

The representation is the elegant part. A complete binary tree fits inside a plain array, with children found by arithmetic. There are no nodes and no addresses at all.

The vocabulary

• Heap property — each parent is smaller than its own children.
• Complete tree — every level filled left to right, with no gaps.
• Sift up — moving a newly added item upward until it is in place.
• Sift down — moving an item downward until it is in place.
• Priority ordering — serving the most urgent item rather than the earliest.
• Heapsort — sorting by repeatedly removing the top.

The mental model

The heap property is weaker than sorting, and deliberately so. Ordering is enforced only between a parent and its own children. Nothing is promised across a level: two siblings' subtrees know nothing about each other. That much weaker promise is still enough to know where the smallest item is. It is at the top, and the property is cheap to maintain after every change.

The storage is the part worth admiring. Fill every level left to right and position and structure agree, which means a child sits at twice the index and a parent at half. So the tree needs no links whatsoever. It is an array, and the tree exists only in the arithmetic.

Maintaining the property takes two moves. On insertion, put the new item at the end and move it up while it is out of order. On removal of the top, move the last item to the front and sink it down. Both walk exactly one path from top to bottom, which is why both cost about the height.

Priority ordering is a *use* of a heap, not a structure of its own, and this is worth being clear about. Serving the most urgent item rather than the earliest is the pattern behind schedulers, event simulation, and several graph algorithms you will meet later. A heap is the usual implementation, and recognising the pattern separately from the implementation is the point.

Heapsort falls out almost for free. Repeatedly remove the top and you get a sorted sequence, in place, with no extra memory. And there is a genuinely surprising result attached. Building the heap costs linear time, not the bound you would guess from doing one insertion at a time. That result is worth working through rather than accepting, because the argument is short and it teaches something about summing costs over a tree.

What you should now be able to explain or do

State the heap property and say why it is weaker than sorting. Explain why a complete tree fits in an array and where children and parents are found. Implement a binary heap with sift up and sift down. Say why both operations cost about the height. Recognise priority ordering as a pattern, separately from the structure implementing it. Explain heapsort, and work through why building a heap is linear.

Check yourself