The heap property and the array layout

Why this matters

Many programs need one answer again and again: "what is the smallest item right now?" A task scheduler wants the task that is due first. A network router wants the packet with the highest priority. A game wants the player with the best score on the leaderboard. New items keep arriving while old ones leave, so you cannot sort everything each time.

A plain sorted list gives you the smallest item at the front, but adding a new item in the middle means shifting many values. An unsorted list makes adding cheap, but finding the smallest means looking at every item. A heap is a structure that gives you both: a cheap insert and a cheap way to get the smallest (or largest) item. Heaps are one of the most useful data structures in interviews, and they show up inside many real libraries.

In this lesson you will learn what a heap is, why its shape makes it fit neatly into an array, and how to find the parent and children of any position with simple arithmetic. You will write a few complete C++ programs along the way. You do not need any prior knowledge of trees. We build the idea from the beginning.

Start with the problem of the smallest item

Suppose you have the numbers 7, 2, 9, 4 and you need the smallest one. You look at all four and pick 2. That takes four looks. If you have a million numbers, it takes a million looks. Nothing is wrong with that for one question. But now suppose you ask the question a thousand times while new numbers arrive between the questions. Looking through everything each time becomes too slow.

You could keep the list sorted. Then the smallest is always the first item. The catch is the insert. If you add 3 to the sorted list 2, 4, 7, 9, you must move 4, 7 and 9 one place to the right to make room. In the worst case that is every item in the list. Sorting after every insert is even more work.

A heap sits between these two extremes. It does not keep everything in full order. It keeps just enough order that the smallest item is always easy to reach, and it can repair that order in a few steps after each insert or removal. "A few steps" here means about the height of a tree, which grows very slowly. A heap of one million items needs only about twenty steps to fix after one change.

Trees, in plain words

Before we can define a heap, we need a few words that programmers use about trees.

A tree is a set of nodes (boxes that hold a value) connected by lines called edges. A tree has one special node called the root, at the top. Every other node has exactly one parent, the node directly above it. A node can have children, the nodes directly below it. A node with no children is a leaf. The level of a node is how far it is below the root: the root is level 0, its children are level 1, and so on. The height of a tree is the number of levels it has.

A binary tree is a tree where each node has at most two children. We call them the left child and the right child. Picture a family tree where each person has at most two children. That is the simplest kind of tree a programmer draws.

Here is a small binary tree with the values written in the boxes:

            2
          /   \
         5     3
        / \   /
       9   6 4

The root is 2. The leaves are 9, 6 and 4. The height is three levels.

The two rules of a heap

A heap is a binary tree that follows two rules.

The first rule is the shape rule. The tree is complete. A complete tree has every level full, except possibly the last level, and on the last level all the nodes are pushed as far left as they can go. There are no holes. If you fill the nodes in reading order from the top, left to right, you never skip a spot.

The second rule is the heap-order rule, sometimes called the heap property. In a min-heap, every parent is less than or equal to each of its children. In a max-heap, every parent is greater than or equal to each of its children.

Here is the shape rule in a picture:

A complete tree with its last level filled from the left, and an incomplete tree with a gap

The left tree in that picture is complete. The right tree is not, because a node sits on the bottom level while a spot to its left is empty. Only complete trees fit the array trick that we will use shortly, so the shape rule is not a formality. It is what makes the whole structure cheap.

The tree in the earlier example, with 2 at the root, is a min-heap. Check each parent against its children. 2 is at most 5 and at most 3. 5 is at most 9 and at most 6. 3 is at most 4. Every parent is small enough. The tree is also complete, because the bottom level holds 9, 6 and 4, and the empty spot would be on the right of 4, which is allowed at the last level. So it is a min-heap.

An everyday picture

Think of a family tree where each person's age is written in their box, and every parent is older than each child. The oldest person sits at the very top. Nobody says anything about two siblings: only the line between a parent and a child matters. This is a max-heap of ages. The oldest value is always at the root, and you can find it in one look.

Flip the rule so that each parent is younger than its children, and you have a min-heap. The youngest sits at the top.

The key idea is this: a heap does not promise that the whole tree is in order. It promises only that every parent beats its own children. That weaker promise is why a heap can be repaired so quickly after a change.

The main consequence

Because of the heap-order rule, the smallest value in a min-heap is always at the root. The root beats its children, and each child beats its own children, so by following the lines down you can never find a smaller value than the root. The same reasoning says the largest value in a max-heap is at the root.

This is the whole reason heaps exist. Asking for the best item costs one look at the root. The rest of the work happens when items are added or removed, and that work is limited by the height of the tree.

Storing a tree in an array

Here is the clever part. A complete tree has no holes, so you do not need pointers to link the nodes. You can store the nodes in a plain array, level by level, from left to right. The root goes at index 0. Its children go next, then the grandchildren, and so on.

Let us number the positions from 0, because C++ arrays and vector start at 0. Here is the tree from the earlier example stored as an array:

A six-value heap drawn as a tree with indexes, and the same six values in one row

Look at the picture. Level 0 holds index 0. Level 1 holds indexes 1 and 2. Level 2 holds indexes 3, 4, 5 (and would hold 6 if it existed). Each level is stored in one run of the array, and the runs follow each other.

Now the question: given an index i, where are its parent and children? Because the array follows the level order, the arithmetic works out. For an index i in a 0-based array:

The division in the parent formula is integer division. Integer division throws away the fraction, so 5 / 2 is 2, not 2.5. In C++, dividing two int values already does integer division, so you get this for free.

Why these formulas work

You do not need to memorize the formulas if you understand where they come from. Level 0 has 1 node. Level 1 has 2 nodes. Level 2 has 4 nodes. Level 3 has 8 nodes. Each level doubles the one above it. The first index of level k is 2^k - 1, because levels 0 to k - 1 hold 1 + 2 + ... + 2^(k-1) = 2^k - 1 nodes in total.

Take index i. Its children sit on the next level. The left child of i is the first child, and each node on a level has two children, one after the other, in the same order. So the children of i are at 2 * i + 1 and 2 * i + 2. The parent is the inverse: if c is a child, the parent is (c - 1) / 2. Check it with index 5 from the example. The parent is (5 - 1) / 2 = 4 / 2 = 2. Index 2 holds 3, and in the tree 4 is a child of 3. Yes, that matches the picture.

Walking through the family of index 4

Here is the family of index 4 in our six-value array:

1. The value at index 4 is 6.
2. Its parent is (4 - 1) / 2 = 3 / 2 = 1. Index 1 holds 5.
3. Its left child would be 2 * 4 + 1 = 9. The array has only six positions (0 to 5), so index 9 does not exist. No left child.
4. Its right child would be 2 * 4 + 2 = 10. That also does not exist.

So 6 is a leaf, and its parent is 5. The tree picture agrees: 6 is a leaf under 5.

Notice that step 3 and step 4 both needed a check. Before you read a[2 * i + 1], you must check that the index is less than the size of the array. In the next program, that check is written out clearly.

A worked example: print every family

Our first program reads an array from the keyboard and prints the parent and children of every index. Type the input in the Input box before you press Run. The first number is the count, and the second line holds the values.

Input to type in the Input box:

6
2 5 3 9 6 4

The program prints one line per index. Here is the exact output for that input:

index 0 value 2 parent none left 1 right 2
index 1 value 5 parent 0 left 3 right 4
index 2 value 3 parent 0 left 5 right none
index 3 value 9 parent 1 left none right none
index 4 value 6 parent 1 left none right none
index 5 value 4 parent 2 left none right none

Read the output carefully. Index 2 has a left child at 5, which exists, and a right child at 6, which does not, because 6 is not less than n, which is 6. Index 3, 4 and 5 are leaves. This is the array version of the tree you saw earlier.

Two details are worth noticing. First, the condition left < n is the check we talked about. Second, the program uses to_string from the <string> header. Without that header, some compilers would give an error about to_string, so it is good practice to include every header you use.

A worked example: check the heap-order rule

Knowing the layout is only half the story. We also need to test whether an array really is a heap. The rule is simple: for every index i greater than 0, the parent must not be larger than the child in a min-heap. We only need to compare each node with its parent. If every node is at least its parent, then by following the lines down, every parent is at most each of its descendants.

Use the same input as before, 6 then 2 5 3 9 6 4. The output is:

min-heap: yes
max-heap: no

Now type 4 and then 9 7 8 2 into the Input box. The array is 9, 7, 8, 2. Index 3 holds 2, and its parent at index 1 holds 7. Since 7 is larger than 2, this is not a min-heap. The program should print min-heap: no. Check the max-heap line too. Index 1 holds 7, its parent holds 9, so that is fine. Index 2 holds 8, its parent holds 9, fine. Index 3 holds 2, its parent 7, fine. So the output is max-heap: yes. Run it and compare.

Notice that the check never needs the right child specifically. Each index i from 1 to the end is a child of exactly one parent, so looping over all children covers every edge in the tree exactly once. That gives a total of n - 1 comparisons, so the check takes time proportional to n.

Why size_t for the loop

The program uses size_t, an unsigned integer type for sizes and indexes. The standard vector::size() returns a size_t. Using the same type avoids a warning about comparing signed and unsigned numbers. The price is that size_t cannot hold a negative number. That is exactly the trap we will meet in the common mistakes section, so keep it in mind.

A worked example: walk up to the root

The parent formula lets you walk up the tree. Starting at any index, you repeatedly jump to the parent until you reach 0. This walk is the basic move of the most important heap operation, which we will meet in the next lesson.

Type 9 into the Input box. Trace the loop by hand:

1. Print 9. Now i is 9, which is greater than 0.
2. i = (9 - 1) / 2 = 4. Print 4.
3. i = (4 - 1) / 2 = 1. Print 1.
4. i = (1 - 1) / 2 = 0. Print 0.
5. i is now 0, so the loop stops.

The output is:

9 4 1 0

This path has four numbers, which means index 9 sits on level 3 of the tree, because the path length from the root is three steps. Every heap index sits on the level equal to the number of times you can halve it and still have something left, which is a clean way to say that the levels grow by doubling.

Try 6 as the input and trace it yourself before you run it. Then try 0, and you should see just 0, because the loop never starts.

How tall is a heap?

The number of levels in a heap decides how many steps a repair can take. If a heap has n nodes, the number of levels is the number of times you can double the count starting from 1 and stay at or below n, counting the first level too. Level 0 is full with 1 node, level 1 with 2, level 2 with 4, and so on. A heap with n nodes needs levels until the total of all filled levels reaches n.

The next program counts levels for the sizes from 1 to 10. It uses a loop that doubles a size until it passes n.

The output has ten lines:

n=1 levels=1
n=2 levels=2
n=3 levels=2
n=4 levels=3
n=5 levels=3
n=6 levels=3
n=7 levels=3
n=8 levels=4
n=9 levels=4
n=10 levels=4

Look at the pattern. The count of levels jumps just after each power of two. Eight nodes fill four levels, one through fifteen fill four levels too, but sixteen would need a fifth level. A heap with one million nodes has only twenty levels, because 2^20 is about one million. That is the reason a heap repair takes about twenty steps and not a million.

If you want a formula, the number of levels is floor(log2(n)) + 1. The logarithm base 2 asks "how many doublings make 2 into n?" You do not need the formula to write code, but it is the reason interviewers say heap operations cost O(log n). We cover Big-O notation in detail in the complexity section below.

What happens in memory

It helps to picture the array in memory. A vector<int> holding six values reserves one block of memory, big enough for six int numbers that are placed side by side. On most computers an int takes four bytes, so the block is 6 * 4 = 24 bytes, with no gaps between values.

Because the values sit side by side, the computer can reach any index with a single multiplication and addition: the address of index i is the start address plus i times four. The formulas for parent and child are also just arithmetic on i. There is no next pointer to follow, no allocation for each node, and no separate box for each value. A tree built with pointers would need a separate allocation and pointer for every node, which costs more memory and makes the processor jump between distant places in memory.

Those jumps matter in practice. Modern processors read memory in chunks called cache lines. Values that sit close together are often already loaded by the time you need them. A heap in an array keeps the nodes of one level next to each other, and the root and its children are close together. This is why array heaps are fast in real programs, even when the complexity is the same as a pointer tree.

The price is that the array must be complete. If you wanted a gap in the middle, you would need a marker value for "empty" and extra space. The complete shape is the bargain that makes the array trick possible.

A heap is not a sorted array

Here is the most common misunderstanding. The array 2, 5, 3, 9, 6, 4 satisfies the heap-order rule for a min-heap, but it is not sorted. The value 5 comes before 3. A heap promises only that the smallest value is at index 0, and that each parent beats its children. Nothing is promised about the order of values on the same level or in different branches.

You can test this yourself. Looking at the array 2, 5, 3, 9, 6, 4, ask whether the second value is the second smallest. The second smallest is 3, which sits at index 2, not index 1. So the array is a valid heap but not sorted. The reason is that heaps only care about the root. Everything else has a looser order.

This looseness is a feature. A sorted array is slow to change because one insert shifts many values. A heap is slow only at the single spot where it needs repair, and each repair walks one path from a leaf to the root or from the root to a leaf. The looseness is exactly what keeps the work small.

Here is a good way to remember it. Sorted order is a line of people standing by height from shortest to tallest. A heap is a family tree where each parent is shorter than each child. In the family tree you can check the whole family by looking only at each parent-child link, and you never need to compare two cousins.

Another way to remember it: a sorted array is always a valid heap. If the array is sorted in ascending order, then every parent comes before its children and so is no larger than them. That is why 1, 2, 3, 4, 5 is a valid min-heap. The reverse is not true. Most heaps are not sorted.

Step through the visualizer above. Watch how the array turns into a tree, and check that every parent is at the top of its children. Notice that the root is always the smallest value in a min-heap, and that moving down one level never shows a smaller value than the level above. As you step, count the indexes of the parent and children, and compare them with the formulas in the table earlier in this lesson.

Complexity: what it costs to look things up

Big-O notation describes how the work grows as the input grows. The letter n stands for the number of items, and O(something) describes the growth rate and ignores constant factors. You will see it throughout this module, so here is what it means for the operations we have seen so far.

Finding the root of a heap costs O(1), because the root is at index 0. Looking at one parent or one child costs O(1), because the formulas are simple arithmetic. Checking whether an array is a heap costs O(n), because you compare each of the n - 1 child positions with its parent once. Counting the levels costs O(log n), because each loop step doubles the size.

The operations that change the heap are where the interesting work lives. Insert and remove both walk a single path of at most about log n steps. The next lesson shows those operations in full. For now, remember the shape: O(1) to peek, O(log n) to change, and O(n) to check everything.

Common mistakes and the messages they produce

Beginners make a small set of mistakes with heaps again and again. Here are the most common ones, with the messages or symptoms you will see.

Mistake 1: using i / 2 as the parent

The formula i / 2 is the parent formula for arrays that start at index 1. If you use it with a 0-based array, index 2 gets parent 1, but index 1 is the root, so the tree is wrong. The correct parent for index 2 is (2 - 1) / 2 = 0. Always check the first few indexes by hand when you write the formula.

Mistake 2: forgetting the size check

If you write a[2 * i + 1] without checking the size, the program reads memory beyond the array. Sometimes this prints garbage numbers. Sometimes the program crashes, and sometimes it seems to work until a larger input breaks it. The safe version is to check first, as the family program did with left < n.

If you use vector::at instead of [], you get an error that names the problem. For this program:

#include <vector>
#include <iostream>
int main() {
    std::vector<int> a = {2, 5, 3, 9, 6, 4};
    std::cout << a.at(7) << "\n";
}

The program stops with a message like this one (the exact wording depends on your compiler library):

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 7) >= this->size() (which is 6)

Read the message from the top. The first line says an out_of_range exception was thrown and not caught. The second line says the index was 7 and the size was 6. That tells you the index is one step too far. In a heap, that often means a child index was not checked against the size first.

Mistake 3: unsigned underflow on index zero

The most surprising bug in this lesson comes from size_t. Suppose you write the parent formula for index 0 without the special case:

The program has no input. Run it and read the output:

without the check: 9223372036854775807
with the check: -1

Here is what happened. size_t is unsigned, so it cannot be negative. When you compute 0 - 1 with an unsigned number, the result wraps around to the largest value of the type. On a typical 64-bit system that is 18446744073709551615. Divide that by two, and you get 9223372036854775807. The code did not crash. It simply produced a huge index, which an array then uses as a bad address. The fix is to check for i == 0 first, which is what the second line does.

Mistake 4: thinking the heap is sorted

If you assume an array is sorted because the root is the smallest, you will write code that scans the array in order and expects the order to hold. It does not. Only the root and the parent-child links are guaranteed.

Mistake 5: mixing up the heap and the memory heap

In C++ you will also hear the word "heap" for the memory that new uses. The two have nothing to do with each other. The memory heap is a region of memory for dynamic allocation. The heap in this lesson is a shape of data. When you read a message or a line of code, check which one is meant.

Debugging walkthrough: the heap check says no

Suppose you wrote the min-heap check and it reports no for an array that should be a heap. Here is a method that works every time.

1. Print the array. Make sure the values are what you typed. A common error is reading the count and then the values in the wrong order.
2. Pick the first index where the check fails. Add a print statement inside the loop, showing i, the parent index and both values. The loop should stop at the first bad pair.
3. Compute the parent by hand for that index, using (i - 1) / 2. Compare your number with the one the program used. If they differ, the formula is wrong somewhere.
4. Check that the comparison is in the right direction. In a min-heap the parent must be smaller or equal, so the failing test is a[parent] > a[i]. Using < instead would flag correct heaps as wrong.

Here is the debugging print added to the min-heap check:

for (size_t i = 1; i < a.size(); i++) {
    size_t parent = (i - 1) / 2;
    cerr << "check index " << i << " parent " << parent
         << " values " << a[parent] << " and " << a[i] << "\n";
    if (a[parent] > a[i]) return false;
}

Run it with the input 6 and 2 5 3 9 6 4. The lines written to cerr show five checks, all passing. If you change the input to 2 5 1 9 6 4, the check at index 2 fails: parent 0 holds 2 and child holds 1. Once you see that, you know exactly which value breaks the rule. This is much faster than reading the whole program and guessing.

Edge cases you should test

A good heap program handles the small cases before the big ones. Test these before you trust a function:

• An empty array. The min-heap check should return true, because there are no parent-child pairs to break the rule. The loop starts at index 1, which is past the end, so nothing runs.
• A single element. Also true. There is no child.
• Two elements in increasing order, such as 1, 2. True for a min-heap. In decreasing order, such as 2, 1, false for a min-heap.
• Equal values, such as 5, 5, 5. True for both min-heap and max-heap, because the rule uses less than or equal to, not strictly less.
• Negative numbers. The heap rule works the same way. The only special thing is that -1 is less than 0, so min-heaps can have negative roots.

Try the empty array in the family program. Type 0 into the Input box and no values. The program prints nothing, which is correct. The min-heap check on an empty array returns true, so it reports yes.

Real-world uses

Heaps appear wherever you need the best item among many that keep changing. An operating system uses a priority queue to choose which process runs next. A printer spooler keeps print jobs in order of urgency. A shortest-path algorithm such as Dijkstra's algorithm keeps the closest unvisited node in a heap. A video game may use a heap to schedule events, because the next event to fire is always at the root. A search engine uses a heap to keep the top few results of a huge list without storing the whole list in order.

Each of those uses depends on one fact from this lesson: the best item is always at the root, and it costs one look to find. The next two lessons show how to keep the heap correct while items arrive and leave.

Interview questions you should be ready for

Interviewers often ask simple questions about heaps to check your understanding of the layout. Here are some of the most common, with short answers.

Where is the minimum in a min-heap? At index 0, the root. You can read it in O(1).

Is a sorted array a min-heap? Yes. In ascending order every parent comes before its children and so is smaller or equal. The reverse is not true, because a heap need not be sorted.

Why is the heap stored in an array and not with pointers? Because the tree is complete. Level-by-level order means the parent and children of any index follow from arithmetic. There is no wasted space and no pointer per node.

What is the height of a heap with n nodes? About log2(n), rounded down, plus one. For one million nodes that is about twenty levels.

How many leaves does a complete heap with n nodes have? About half of them. The leaves are the indexes from n / 2 to n - 1. This fact is useful later for building a heap quickly.

Pause on the last question. A leaf has no children, so 2 * i + 1 must be at least n. Solve 2 * i + 1 >= n and you get i >= (n - 1) / 2, so the leaves start at about n / 2. You will use this again in the next lesson.

Variations on the layout

Some programs number the heap from index 1 instead of index 0. Then the formulas become simpler: the parent of i is i / 2, the left child is 2 * i, and the right child is 2 * i + 1. Textbooks often use this version because the arithmetic is clean. In C++ with vector, index 0 is the natural start, so the formulas in this lesson are the ones you will use. If you read another book and see i / 2, check where its indexes start before you copy it.

Another variation is a d-ary heap, where each node has up to d children instead of two. The same array trick works, with child formulas based on d. You will rarely need it in an interview, but it shows that the array layout is about the complete shape, not about the number two.

Practice

Each exercise below uses the same ideas as the lesson. Try each one on paper first, then check with the hidden solution or with a program.

1. For index 6 in a 0-based heap, write its parent, its left child and its right child.

2. Is 1, 3, 2, 7, 4, 2 a min-heap? Check each parent and child by hand. Hint: look at index 5 and its parent.

3. Is 5, 4, 3, 2, 1 a min-heap? Is it a max-heap? Explain your answer in one sentence each.

4. Change isMinHeap into isMaxHeap in the first check program, and run it on 9, 7, 8, 2. What does it print?

5. Write a function int parentIndex(int i) that returns -1 when i is 0 and the parent index otherwise. Test it for indexes 0 to 6.

int parentIndex(int i) {
    if (i == 0) return -1;
    return (i - 1) / 2;
}

6. A heap has 11 nodes. How many levels does it have? How many leaves?

7. Write a program that reads n and then n integers and prints yes if the array is sorted in ascending order and no otherwise. Then argue whether every sorted array is a min-heap.

8. Explain in your own words why size_t underflow on i = 0 causes a problem only in the parent formula, not in the left-child formula.

9. Print the family table from the first program for a heap of seven values 7, 1, 5, 3, 9, 4, 6. Check the output by hand for indexes 2 and 6.

10. Using the loop in the parent-walk program, describe in one sentence what it prints for input 1, and for input 2.

11. Look at this claim: "In a heap, every index from n / 2 to n - 1 is a leaf." Test it for n = 6 and n = 7.

What you now know

• A heap is a complete binary tree with a heap-order rule: in a min-heap each parent is at most each child, and in a max-heap each parent is at least each child.
• The smallest value of a min-heap, or the largest of a max-heap, is always at the root, index 0.
• The tree is stored level by level in a vector. The parent of index i is (i - 1) / 2, and the children are 2 * i + 1 and 2 * i + 2, with a size check before each read.
• A heap is not fully sorted. Only the parent-child links are ordered, and a sorted array is always a valid min-heap.
• The number of levels grows with the logarithm of the size, so operations that walk one path cost O(log n).
• Watch out for size_t underflow when you subtract from zero, and for out-of-range indexes. The next lesson uses these formulas to insert and remove items.