Understanding a Heap

Understanding a Heap

A little while ago we met the idea of a priority queue — a line where the most important item always comes out first, no matter when it joined. That idea is great, but how do we actually build it so it runs fast? The most popular way is to use a special structure called a heap.

What is a heap?

A heap is just a tree that follows one special rule. We call that rule the heap property. A tree is simply a way of connecting items where one item sits on top and others branch out below it, like a family tree.

You can build a heap using different kinds of trees, but the most common one uses a binary tree — a tree where every item has *at most two* children below it (a left child and a right child). A heap built from a binary tree gets a special name: a binary heap. That is the only kind we will study here.

For a binary tree to count as a binary heap, it must obey two conditions:

1. The tree is a complete binary tree.
2. It follows the heap ordering property.

Let's understand both, one at a time.

Condition 1: A complete binary tree

Picture the tree drawn in rows from top to bottom. Each row is called a level. The top item sits alone on level 0, the next row is level 1, and so on.

A tree is complete when:

• Every level is completely filled with items, *except possibly the very last level*.
• On that last level, the items are pushed as far to the left as possible — no gaps, then fill left to right.

So you fill the tree the same way you would seat people in a theater: finish one row fully before starting the next, and within a row always take the left-most empty seat first.

Why does this matter? Because a completely filled, left-packed tree has no holes. That keeps the tree short and balanced, which is exactly what makes a heap fast. It also lets us store the whole tree neatly inside a plain array later on.

Condition 2: The heap ordering property

This is the rule that makes a heap so good at its job. It is a condition placed on every single node in the tree, and it says:

> A node has higher priority than both of its children.

In other words, a parent is always "more important" than the two items hanging directly below it. Look at the small picture: the top node is the higher priority item, and both nodes beneath it are lower priority.

If this is true everywhere — for *every* parent and its children — then something wonderful follows: the single most important item in the whole tree must sit at the very top, the root. It cannot be anywhere else, because any item that had higher priority than the root would have to be its ancestor, and the root has no ancestor.

That is the magic. Whenever you ask the heap "who is most important right now?", the answer is always sitting right at the top, ready to be picked up instantly. This is why inserting new items and pulling out the highest-priority item are both very efficient in a heap, much faster than searching through an ordinary tree.

Putting it together

A binary heap is a complete binary tree (no gaps, packed to the left) that also keeps every parent more important than its children. The two rules work as a team: the "complete" rule keeps the tree short and tidy, and the "ordering" rule keeps the most important item always on top.

Note that "higher priority" can mean different things. If bigger numbers are more important, the largest value sits on top — that is called a max-heap. If smaller numbers are more important, the smallest sits on top — a min-heap. Either way, the same heap property is doing the work.