Heapify
- Algorithms course
- Intermediate
- Lesson 10/80
- 4 min
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.
Practice 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).
Starter code
def heapify(arr, n, i):
# Sift downSample 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)Expected output
[9, 4, 5, 1, 3, 2]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Larger child
largest = i
if arr[left] ____arr[largest]:largest = i
if arr[left] >arr[largest]:Explanation: > is right.
2 Heapify: match the terms
| Term | Meaning |
|---|---|
Heapify |
Sift down |
Larger child |
Swap |
Leaf |
Base case |
Cost |
O(log n) |
3 When does heapify stop?
- Always at the root
- Only at a leaf
- At a leaf or when satisfied Correct answer
- Never
Explanation: At a leaf or when satisfied