Heapify and Sift
Heaps: lesson 2 of 4
One wrong value walks a single path back into place.
Lesson 2 of 4 · 6 min
Heapify and Sift
Step 1 of 14
A raw pile, not a heap. Fixing it never touches the whole array — each wrong value walks one path.
The Idea
Fixing a heap never touches the whole array. A value that is too big sinks toward the leaves, swapping with its smaller child; a value that is too small rises toward the root. Either way it walks one path — at most log n swaps.
To build a heap from a raw pile, sift down starting at the last parent and work backward. That is O(n), because most nodes are already near the bottom.
Real-World Example
A water treatment works settling tank does this without anyone stirring it. Heavy silt sinks one layer at a time until it meets something heavier; froth rises until it meets something lighter. Nothing is compared with the whole tank — each particle only negotiates with its immediate neighbours.
The Code
def sift_down(h, i):
n = len(h)
while 2 * i + 1 < n: # while a left child exists
c = 2 * i + 1
if c + 1 < n and h[c + 1] < h[c]:
c += 1 # take the smaller child
if h[i] <= h[c]:
break # parent already beats both
h[i], h[c] = h[c], h[i]
i = c # follow the value down
pile = [9, 4, 7, 1, 3]
for i in range(len(pile) // 2 - 1, -1, -1):
sift_down(pile, i) # last parent first, O(n) total
print(pile) # [1, 3, 7, 4, 9]Your turn
Put the steps in the right order.
- Swap them, then continue from the child's position
- Start at the last parent, just above the bottom row
- Step one index to the left and repeat until index 0 is done
- Compare the node with the smaller of its two children
Mini quiz
1 / 3