Insert
- Algorithms course
- Intermediate
- Lesson 38/80
- 4 min
Add at the end, sift up to restore the heap.
Insert
When inserting into a heap, the element is first appended to the end, then sifted up: if smaller than its parent (min-heap) it swaps, continuing to the root.
Each step goes up one level; total O(log n). After insertion the heap property is preserved.
Sift-up continues until the new element finds its correct place; in the worst case it reaches the root.
Sift-up steps
Sift-up: i is the new element's index. parent = (i-1)//2. If arr[i] < arr[parent] swap, set i = parent, repeat.
Continue until i == 0 (root) or the element is >= its parent. This restores the min-heap property.
Each swap goes up one level; at most log n swaps are done.
Practice Sift-up (insert)
Write sift_up(arr, i). Sift up for a min-heap. Print [0, 1, 2, 3] with arr = [1, 3, 2, 0]; sift_up(arr, 3); print(arr).
Starter code
def sift_up(arr, i):
# Sift upSample solution
def sift_up(arr, i):
# Sift up
while i > 0:
parent = (i - 1) // 2
if arr[i] < arr[parent]:
arr[i], arr[parent] = arr[parent], arr[i]
i = parent
else:
break
arr = [1, 3, 2, 0]
sift_up(arr, 3)
print(arr)Expected output
[0, 1, 2, 3]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Sift-up comparison
while i > 0 and arr[i] ____arr[parent]:while i > 0 and arr[i] <arr[parent]:Explanation: < is right.
2 Insert: match the terms
| Term | Meaning |
|---|---|
Sift-up |
Shift up |
Parent |
(i-1)//2 |
Swap |
Exchange |
Cost |
O(log n) |
3 When does sift-up stop?
- Always at the root
- Only at a leaf
- At root or >= parent Correct answer
- Never
Explanation: At root or >= parent