The heap property and array layout in Python

Why it matters

Many programs ask one question again and again: "What is the smallest item right now?" A print server wants the next job to run. A route planner wants the nearest city it has not visited. A game wants the next event on its timeline. You could keep a plain list and search it each time. That costs time proportional to the length of the list, and the work repeats on every question. You could keep the list fully sorted. Then the answer is quick, but adding one new item can force you to shift many others.

A heap sits in the middle. It finds the smallest item quickly, and it adds new items quickly. Both operations take about log n steps, where n is the number of items stored. For a million items, log n is about 20 steps. That is a small number of steps for a large list.

In this lesson you learn the rule a heap follows. You learn how the tree is stored in a plain Python list, and how the two basic operations, insert and remove the smallest, work. You will write a working heap as a Python class and trace it by hand. Lesson 2 uses the standard library module heapq, which gives you a heap without writing one.

Start with a waiting room

Picture a hospital waiting room. Patients arrive in any order. The nurse does not call them in arrival order. She calls the sickest patient first, whoever arrived earlier. When a new patient comes in, she does not reorder the whole room. She only needs to know who is at the front, and who would be next after that.

That is the core idea of a heap. A heap keeps just enough order to answer "who is first?" quickly. It does not keep everything sorted, because that extra work is not needed for the question.

The nurse's rule is also a good model for the data structure. The most urgent patient is at the front. Every other patient is somewhere behind, and the exact order behind the front is not kept.

The words you need

Before the rules, define the terms in plain words.

A tree is a set of nodes joined by lines called edges. Nodes hold values. One special node sits at the top. It is the root. Every other node has exactly one parent directly above it. A node can have children below it. A node with no children is a leaf.

A binary tree is a tree where each node has at most two children. People call them the left child and the right child.

The level of a node is how many edges it is from the root. The root is at level 0. The height of a tree is the longest path from the root down to a leaf, counted in edges. A tree with only a root has height 0.

A complete tree has every level full, except possibly the last one. The last level fills from the left, with no gaps. Picture building a tree of people in rows: you fill row by row, left to right, and you only start a new row when the one above is full.

A heap is a complete binary tree that also follows the heap property, described next.

A min-heap is a heap where the smallest value sits at the top. A max-heap is a heap where the largest value sits at the top. Both are the same shape. Only the comparison is flipped.

The heap property, precisely

The heap property is the rule that gives a heap its power. For a min-heap, every parent is less than or equal to each of its children. For a max-heap, every parent is greater than or equal to each of its children.

Notice what the rule does not say. It only compares a parent with its own children. Two children of the same parent can be in any order. Two nodes on different branches can be in any order. The only guaranteed fact is this: the root of a min-heap is the smallest value in the whole tree. Everything else is partly ordered.

Here is a min-heap with six values:

        2
      /   \
     5     3
    / \   /
   9   6 4

Check each parent against its children. The root 2 is at most 5 and at most 3. The node 5 is at most 9 and at most 6. The node 3 is at most 4. Every rule holds, so this is a valid min-heap. Notice that the bottom row is not sorted: 9 sits left of 6, and 6 is bigger than 4. The tree does not need to be sorted, because the rule only links parents to children.

Now change one value. Put 1 where the 9 was, but keep the rest. The node 5 now has a child 1, and 5 is bigger than 1. The heap property is broken. The tree is no longer a min-heap, even though the root is still the smallest value.

Why the shape must be complete

Two rules make a heap fast: the heap property and the complete shape. The shape is the less obvious one, so take a moment with it.

In a complete tree, the height is about log2 n. Here is a small table you can check by counting levels:

Each new level doubles the number of items that fit. Seven items fill three levels. Fifteen items fill four levels. A million items fill about twenty levels. So any path from the root to a leaf is short, and any operation that walks a path is short too.

The shape also has a practical benefit. A complete tree has no holes. Every position from index 0 up to the last item is in use. That means the whole tree can be stored in a plain list with no empty slots and no pointers between nodes. You will see that next.

Storing the tree in a list

Store the tree one level at a time, from top to bottom and left to right. The root goes at index 0. The next level goes at indexes 1 and 2. The level after that goes at indexes 3 through 6, and so on. The index of an item in the list tells you where it sits in the tree, if you know the formulas.

For a node at index i:

The // operator is floor division. It divides and throws away the fraction. In Python, 7 // 2 is 3, and 7 / 2 is 3.5. Use // for every index in this lesson. A single / gives a float, and a list cannot be indexed with a float. You will see that error in the mistakes section.

Here is the table for the first seven positions:

The formulas follow from the order of the list. The children of the root come first in the second level, so they get the first two slots after the root: indexes 1 and 2. The children of index 1 come next, so they get indexes 3 and 4. The children of index 2 come after them, at 5 and 6. The pattern is that each node's children are the next two unused slots, in the order their parents appear. Counting that out gives 2 * i + 1 and 2 * i + 2.

There is one trap, and Python makes it quieter than most languages do. The root has no parent. If you plug index 0 into the parent formula, you get (0 - 1) // 2. Floor division rounds toward negative infinity, so the answer is -1, not 0. Python does not raise an error for -1 as an index. It reads the last item of the list. So the formula gives a wrong parent without any warning. The program below shows this. You must check for the root yourself.

Runnable example: a calculator for positions

The first runnable block works out the family of one index. It prints the parent and the two children of index 4. It also shows the root trap.

The output is:

index 4
parent: 1
left child: 9
right child: 10
(0 - 1) // 2 in Python is -1
data[(0 - 1) // 2] is 9
data[-1] is 9
(0 - 1) / 2 is -0.5

Read the output carefully. The parent of index 4 is index 1, because (4 - 1) // 2 is 3 // 2, which is 1. Its children are 9 and 10. The rest of the output shows the trap. (0 - 1) // 2 is -1, and data[-1] quietly returns the last item, 9. No error is raised. That is why the function checks i == 0 first. The last line shows that / would give a float, -0.5, which is never a valid index.

Worked example 1: family members of index 4

Work this one by hand, without the program. You have a list of eleven values. You want the family of the item at index 4.

Step 1. Find the parent. Use (4 - 1) // 2. That is 3 // 2, and the fraction is dropped, so the parent is index 1.

Step 2. Find the left child. Use 2 * 4 + 1, which is 9. Index 9 is the left child.

Step 3. Find the right child. Use 2 * 4 + 2, which is 10. Index 10 is the right child.

Step 4. Check the bounds. The list has eleven values, so indexes 0 through 10 exist. Both children exist. A node at index 5 or higher in a list of eleven would have no children at all, because 2 * 5 + 1 is 11, which is past the last index.

The check in step 4 is the one beginners skip. Every loop that looks at a child must first check that the child index is smaller than the number of items. You will see this check again in every heap operation.

Worked example 2: is this list a heap?

Take the list [2, 5, 3, 9, 6, 4]. Write the pairs of parent and child. For each non-root index i, the parent is (i - 1) // 2.

Every row says yes, so this list is a valid min-heap.

Now take [2, 5, 3, 1, 6, 4]. Only one value changed: index 3 is now 1 instead of 9. Check the same rows. The row for index 3 has parent index 1, value 5, and child value 1. Five is not at most one, so the rule breaks there. The list is not a heap.

The next runnable block does this check for any list. It returns the first pair that breaks the rule and says which indexes broke it.

The output is:

valid min-heap
not a min-heap: values[1] = 5 is larger than its child values[3] = 1
valid min-heap
valid min-heap
valid min-heap

The loop walks the children in index order. It checks each child against its parent, so the first broken pair is the one reported. The loop never checks the root as a child, which is correct because the root has no parent. An empty list and a one-item list have no pairs to check, so both are valid. The third line is worth a look: [1, 3, 8, 5, 6] is a valid heap even though it is not sorted, because 8 comes before 5.

Insert: sift up

Now the first real operation. You want to add a new value and keep the heap property.

The rule is short. Append the new value to the end of the list, in the next free slot. That keeps the tree complete. Then compare it with its parent. If the new value is smaller than its parent, swap them. Repeat with the new parent position until the value is not smaller, or until it reaches the root. This movement upward is called sift up. "Sift" means to move a value through the tree until it is in the right place.

The end is the right place to start. The complete shape leaves exactly one free slot in the next position. Any other place would leave a hole in the tree. The value only needs to move up, because it was placed at the bottom. Only the path from that position to the root can be broken by the new value. Every other parent-child pair is unchanged.

The number of swaps is at most the height of the tree, so insert costs O(log n) time.

Worked example 3 traces this step by step. Start with [3, 5, 8], which is a valid min-heap. Add 1.

Step 1. Append 1 at index 3, the next free slot. The list is [3, 5, 8, 1]. Its parent is index (3 - 1) // 2 = 1, which holds 5. Since 1 is smaller than 5, swap them. The list is [3, 1, 8, 5].

Step 2. Now 1 is at index 1. Its parent is index 0, which holds 3. Since 1 is smaller than 3, swap them. The list is [1, 3, 8, 5].

Step 3. Now 1 is at index 0. It has no parent, so the loop stops. The list [1, 3, 8, 5] is a valid min-heap. The new minimum is at the top.

Only two swaps happened, and the list has four items. The number of comparisons was small because the path from index 3 to the root has only two steps. For a much bigger heap, the path is still only about log n long.

Writing the heap in Python

Now write the whole thing in Python. The class is named MinHeap. It keeps its items in one list, self.data. It has add for insert, poll for remove the smallest, peek to look at the smallest without removing it, size, and is_empty.

A few Python words come up here. A class groups some data and the functions that work on it. The data lives in attributes, such as self.data. A method is a function inside a class. The first parameter of a method is always self, which means the object the method was called on. __init__ is the method Python runs when you create a new object. A name that starts with one underscore, such as _sift_down, is a convention that says "this is for use inside the class". Python does not stop you from calling it, but you should not.

The last part of the program adds five numbers, prints the list after each add, and then removes everything.

The output is:

add 5 -> [5]
add 3 -> [3, 5]
add 8 -> [3, 5, 8]
add 1 -> [1, 3, 8, 5]
add 6 -> [1, 3, 8, 5, 6]
size 5
peek 1
poll 1
poll 3
poll 5
poll 6
poll 8
error: heap is empty

Read the add lines against Worked example 3. The line add 1 -> [1, 3, 8, 5] is exactly the result of the two swaps. The add 6 line shows a case with no swap: 6 is placed at index 4, its parent at index 1 holds 3, and 3 is not bigger than 6. So nothing moves.

Notice that the output lists the values in list order, not sorted order. Only the sequence of poll lines is sorted. That is the heap promise: each poll returns the smallest remaining value. The try and except lines at the end run poll and catch the error it raises on an empty heap, so the program prints the message instead of stopping.

The type hints such as value: int and -> None do not change how the code runs. Python ignores them. They tell a reader, and a checking tool, what kind of value each function expects. list[int] means a list whose items are integers.

The poll method comes next.

Remove the minimum: sift down

Removing the smallest value is harder, because there is a hole at the top. The rule is this. Take the last value in the list, move it to the top, and remove it from the end. Now the top may be bigger than its children. Compare it with its smaller child. If the child is smaller, swap them. Repeat moving down until the value is not bigger than its children, or until it has no children. This downward movement is called sift down.

There is one key detail: compare with the smaller child, never the bigger one. In a min-heap, the smaller child is the one allowed to rise. If you swapped with the bigger child, the smaller child would end up below it, and the rule would break. Sift down also needs both child checks, because the moved value may need to go left or right.

Worked example 4 traces a poll on [1, 3, 8, 5, 6], which is the heap from the add example.

Step 1. Save the top, 1, as the answer. Remove the last value, 6, from the end of the list, and put it at index 0. The list holds [6, 3, 8, 5].

Step 2. At index 0, the value is 6. Its children are index 1 (value 3) and index 2 (value 8). The smaller child is 3. Since 6 is bigger than 3, swap. The list is [3, 6, 8, 5].

Step 3. Now 6 is at index 1. Its children are index 3 (value 5) and index 4. Index 4 is past the end, because the list has four items and the last index is 3. So only index 3 counts, with value 5. Since 6 is bigger than 5, swap. The list is [3, 5, 8, 6].

Step 4. Now 6 is at index 3. It has no children, because indexes 7 and 8 are past the end. The loop stops.

The answer is 1, and the new list is [3, 5, 8, 6], which is a valid heap.

Each swap moves the value one level down. The height limits the number of swaps, so poll costs O(log n) time. The code checks left < size and right < size before reading a child. Without those checks, the code would read a slot past the end and stop with an IndexError.

Step through it yourself

Use the visualizer below to watch a min-heap change. The default commands are the same five inserts and two removals from the examples above. An outlined node is being compared. A filled node was just swapped. Change the commands and press Play to try your own.

Watch two things. First, after each insert, the smallest value is at the top. Second, after each removal, the top becomes the next smallest. You should see extract return 1 and then 3, which matches the traces in this lesson. After those two removals, the heap holds 5, 6 and 8.

What happens inside the computer

A Python list is a row of slots. Each slot holds a reference, which is a pointer to an object somewhere else in memory. Each int is an object. So the list does not store the number itself in its slot. It stores the address of the number. Reading data[i] follows that pointer, and it takes one step, the same as reading a slot in a fixed array. That is why the index formulas are cheap: the code can jump to any slot directly, with no tree nodes to follow.

A tree built from separate node objects would work differently. Each node would be its own object, and finding a child would mean following a reference from one node to the next. The list layout avoids that cost. Each parent and child is found by arithmetic on the index alone.

When append runs out of room, Python allocates a bigger block and copies the pointers into it. The standard CPython implementation grows the list by a share of its current size, not by one slot. One append that triggers a copy costs O(n). But the growth happens rarely. Averaged over many appends, each append costs O(1) time. That idea is called amortized cost. You do not manage this growth yourself, and you do not check for a full list. The add method above has no size check for that reason.

The call stack is simple here. Each method call adds a small frame: add calls no method of its own, and poll calls peek and _sift_down. There is no recursion. The loops in add and _sift_down are plain while loops. Python has a limit on how deep recursion can go, by default about 1000 calls. A recursive version of sift down would use one call per level, so for a heap with a million items it would only need about 20 calls. The loop version uses no extra calls at all, so the limit never matters here.

Runnable example: watch the sift up

The next block prints every swap during an insert. It adds five values in order and prints each step, so you can follow the value 1 as it rises.

The output is:

placed 9 at index 0: [9]
placed 4 at index 1: [9, 4]
  swap with parent at index 0: [4, 9]
placed 7 at index 2: [4, 9, 7]
placed 1 at index 3: [4, 9, 7, 1]
  swap with parent at index 1: [4, 1, 7, 9]
  swap with parent at index 0: [1, 4, 7, 9]
placed 3 at index 4: [1, 4, 7, 9, 3]
  swap with parent at index 1: [1, 3, 7, 9, 4]
final: [1, 3, 7, 9, 4]

Follow the value 1. It is placed at index 3, swaps with 9 at index 1, then swaps with 4 at index 0. Only the path from the new slot to the root changes. The value 7 at index 2 never moves, because it was never on that path. Use this trace whenever you are unsure what a sift up does.

The line a, b = b, a is the Python way to swap two values. The right side is built first, from the old values, and then both names are assigned. You do not need a temporary variable.

Common mistakes and the messages they produce

Beginners make the same few mistakes with heaps. Each mistake has a message you can recognise, so learn them now. When Python stops with an error, it prints a traceback, which is a list of the lines that were running when the error happened. The last line of the traceback holds the error type and the message. Read that line first.

Mistake 1: thinking the list is sorted. The list [1, 3, 8, 5, 6] is a valid heap, but it is not sorted, because 8 comes before 5. A heap only promises parent-child order. If your code assumes the whole list is in order, a test with a sorted-looking example will pass, and a different example will fail. Always print the list and check the parent-child pairs.

Mistake 2: using the 1-based formulas. Some textbooks start the list at index 1. Then the children of i are 2 * i and 2 * i + 1. Mixing the two systems gives wrong children. In this lesson the list starts at 0, so use 2 * i + 1 and 2 * i + 2. If you use 2 * i with a 0-based list, the left child of index 0 would be index 0 itself, so the links from the root down would be wrong.

Mistake 3: using / for the parent. In Python, / always gives a float. So (i - 1) / 2 gives 1.0, not 1. A list cannot be indexed with a float, and Python stops with this message:

TypeError: list indices must be integers or slices, not float

The fix is //. Use floor division for every index.

Mistake 4: popping from an empty heap. A poll that calls self.data.pop() on an empty list fails with this line at the end of the traceback:

IndexError: pop from empty list

The fix is to check is_empty() first, as peek does. The class in this lesson calls peek at the start of poll, so it raises the clearer IndexError with the message heap is empty.

Mistake 5: reading a child that is past the end. A Python list has exactly as many slots as items, so reading past the end raises an error:

IndexError: list index out of range

This is loud, which is good. The quiet version of this bug happens only if you keep spare slots in the list, with a separate size counter, as some array-based heaps do. Then a child index past the live part can read an old value and return a wrong answer with no error. In that design, check the child index against the size, not against the length of the list.

Mistake 6: sifting down toward the larger child. In a min-heap, the swap must pick the smaller child. If you pick the larger one, the smaller child ends up above a bigger value, and the heap property breaks. The wrong result is often a poll that returns a value that is not the smallest.

Mistake 7: the negative index trap at the root. Covered above. (0 - 1) // 2 is -1, and data[-1] reads the last item without any error. Check i == 0 before you use the parent formula.

Debugging walkthrough

Suppose a classmate says their heap returns the wrong poll order. Here is a method you can use on any heap bug.

Start by printing the list after each add. Use the checker from the runnable block above, or print the list directly. Look at the first time the printed list breaks the rule. If the first break happens right after an add, the bug is in the sift up. If the first break happens after a poll, the bug is in the sift down.

Next, trace the operation by hand, using the same list. Write each step and the index formulas. Compare your trace with the code line by line. Most bugs are in one of three places: the parent formula, the child formula, or the loop condition.

Finally, check the boundaries. Ask what happens when a child index equals the size, when the heap has one item, and when the heap is empty. The bug in mistake 5 shows up only at the boundary. A correct heap must work for one item and for a long list.

Here is a short example. A student wrote this code for sift down:

left = 2 * i + 1
if data[left] < data[i]:
    data[i], data[left] = data[left], data[i]

It looks harmless. It fails in two ways. It never picks the smaller of two children, and it reads data[left] even when left is past the end. Python raises IndexError in the second case, so the error is at least visible. The fix is the full pattern from _sift_down above, with both bounds checks and a smallest variable.

Variations and edge cases

An empty heap has no smallest value. Decide what peek and poll do when there is nothing to return. The class here raises an exception, which tells the caller something went wrong. The standard library's heapq raises IndexError too. Some other designs return None instead. Both designs are fine, but you must choose one and document it.

A heap with one item has no sifting to do. add stores the value and the loop stops at once. poll removes the one value, the list is empty, and the if self.data: check skips the sift.

Duplicates are allowed. A heap can hold the same value many times. The order among equal values is not promised. If two tasks have the same priority, a plain heap may return them in either order. Lesson 2 shows how to break ties.

Negative numbers work without change, because the comparison does not care about sign.

A max-heap is the same code with the comparisons flipped. Change self.data[(i - 1) // 2] > self.data[i] to self.data[(i - 1) // 2] < self.data[i], and change the child tests the same way. You can also store the negatives of the values in a min-heap. That trick works in Python, and it is the method lesson 2 uses with heapq. Python integers have no largest value, so negating any integer is always safe.

A heap of objects works the same way. Instead of numbers, store tuples or objects and compare one field. Lesson 2 shows tuples, which Python compares one item at a time, and a dataclass.

Interview questions and real uses

Interviewers often ask simple questions about heaps. You should answer them in one or two sentences, and back them with the reason.

"What is the cost of finding the minimum in a heap?" It is O(1), because the minimum is always at index 0. "What is the cost of an insert?" It is O(log n) in the worst case, because the new value can rise to the root. Averaged over random inputs, the cost is often much less, but the worst case is what you should state. "Why not keep a sorted list?" Because inserting into a sorted list shifts many values, which is O(n) per insert.

"Why does a heap use a list?" Because the tree is complete. The list has no gaps, so the index formulas find every parent and child in constant time, with no pointers.

Heaps show up in many real systems. An operating system picks the next process to run by priority. A shortest-path algorithm called Dijkstra's algorithm keeps the closest unvisited node in a min-heap (module 24 covers graphs). Huffman coding, used in file compression, builds its code tree by repeatedly taking the two smallest items from a heap (module 25 covers greedy methods). An event simulator always runs the earliest event next.

Complexity summary

Practice

Exercise 1. Draw the min-heap after adding 7, 1, 8, 3, 2 in that order. Show the tree and the list after every add. Hint: sift up after each add.

Show the answer

After 7: [7]. After 1: 1 goes to index 1 and swaps with 7, giving [1, 7]. After 8: index 2, parent 1 is smaller, so [1, 7, 8]. After 3: index 3, parent index 1 holds 7, swap gives [1, 3, 8, 7], then parent index 0 holds 1, which is smaller, so stop. After 2: index 4, parent index 1 holds 3, swap gives [1, 2, 8, 7, 3], then parent index 0 holds 1, so stop. Final list: [1, 2, 8, 7, 3].

Exercise 2. In a list-based heap that starts at index 0, what are the parent and the two children of index 4?

Show the answer

The parent is (4 - 1) // 2, which is 1. The children are 2 * 4 + 1 = 9 and 2 * 4 + 2 = 10. Check the length of the list before you read them.

Exercise 3. Remove the minimum from [1, 3, 2, 7, 4] by hand. Write the list after each step.

Show the answer

Save 1. Remove the last value, 4, and put it at index 0, giving [4, 3, 2, 7]. The children of index 0 are 3 and 2. The smaller is 2 at index 2, so swap, giving [2, 3, 4, 7]. Index 2 has children at 5 and 6, which are past the end of a four-item list, so stop. Final list: [2, 3, 4, 7].

Exercise 4. Is [1, 4, 2, 9, 5, 3, 8] a valid min-heap? Check every parent-child pair and say which indexes you checked.

Show the answer

Yes. The pairs are: index 1 (4) under index 0 (1); index 2 (2) under 0; index 3 (9) under 1 (4); index 4 (5) under 1 (4); index 5 (3) under 2 (2); index 6 (8) under 2 (2). Every parent is at most its children.

Exercise 5. In [1, 2, 3, 0, 5], at which index does the heap property first break, and which parent is involved?

Show the answer

Index 3 holds 0. Its parent is index 1, which holds 2. Since 2 is bigger than 0, the rule breaks at index 3, with parent index 1.

Exercise 6. Write a function that returns the index of the last non-leaf node in a heap of size n. Test it for sizes 1, 2 and 10.

Show the answer

The answer is n // 2 - 1. For n = 1, the result is -1, which means there are no non-leaf nodes. For n = 2, the result is 0, because index 0 has child 1. For n = 10, the result is 4, because index 4 has child 9 and index 5 has no child.

Exercise 7. Add a clear() method to the MinHeap class in the runnable block that removes every value. After clear(), add must still work.

Show the answer

def clear(self) -> None:
    self.data = []

It replaces the list with an empty one. add then appends to the new list as usual.