Heapify

Sift a node down to restore the heap property.

Heapify

Heapify fixes a node that violates the heap property by sifting it down. The node is compared with its two children and swapped with the larger one.

Repeating this for every non-leaf node, from the last to the root, turns the whole array into a max-heap. This takes O(n).

Heapify is the foundation of heap sort and the priority queue.

Recursive heapify

Heapify can be written recursively: swap the node with the larger child, then apply the same to that child. The base case is a leaf node.

An iterative version is also common and avoids stack overflow. Both run in O(log n) because each step goes down one level.

On large arrays iterative is preferred; on small ones recursion is readable.

Exercise Heapify (sift down)

Write heapify(arr, n, i). Sift node i down for a max-heap. Print [9, 4, 5, 1, 3, 2] with arr=[3,9,2,1,4,5]; heapify(arr,6,0); print(arr).

Show example solution

def heapify(arr, n, i):
    # Sift down
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
arr = [3, 9, 2, 1, 4, 5]
heapify(arr, 6, 0)
print(arr)

Test yourself

Larger child

largest = i
if arr[left] ____arr[largest]:

Show answer

largest = i
if arr[left] >arr[largest]:

Heapify: match the terms

Heapify

Sift down
Larger child

Swap
Leaf

Base case
Cost

O(log n)
When does heapify stop?
- Always at the root
- Only at a leaf
- At a leaf or when satisfied
- Never
Show answer

At a leaf or when satisfied — At a leaf or when satisfied

Next lesson: Build heap and sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies