Building a heap

Turning an array into a heap by pushing each element is O(n log n), but sifting down from the last parent to the root does it in O(n). heapify is how libraries do it, and why it is cheaper than sorting.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain why heapify from the last parent is O(n)
Compare building a heap by pushes with heapify
Spot the sift-down pass that starts at the root

In practice

A few lines that show Building a heap doing its job.

Python

def heapify(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # last parent down to root
        sift_down(a, i, n)

def sift_down(a, i, n):
    while True:
        smallest, l, r = i, 2 * i + 1, 2 * i + 2
        if l < n and a[l] < a[smallest]: smallest = l
        if r < n and a[r] < a[smallest]: smallest = r
        if smallest == i: return
        a[i], a[smallest] = a[smallest], a[i]
        i = smallest

The common mistake

Watch for

Starting sift-down from index 0 and going up. Children must already be heaps before their parent is fixed, so the pass runs from the last parent back to the root.

What to know first

Your roadmap puts these before Building a heap, unless you already know them.

Heap operations

How it stays learned

Once a session shows you understand Building a heap, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

The review card

What you are asked on review day.

Data Structures & Algorithms · Heaps and priority queues

What is the time complexity of building a heap from an unsorted array?

Show answer

O(n). Sifting down from the last parent to the root does less work at the lower levels, and the total sums to linear time — not O(n log n).

Previous in the module← Heap operations

Next in the moduleTop-k problems →