Insert

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.

Exercise 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).

Show example 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)

Test yourself

Sift-up comparison

while i > 0 and arr[i] ____arr[parent]:

Show answer

while i > 0 and arr[i] <arr[parent]:

Insert: match the terms

Sift-up

Shift up
Parent

(i-1)//2
Swap

Exchange
Cost

O(log n)
When does sift-up stop?
- Always at the root
- Only at a leaf
- At root or >= parent
- Never
Show answer

At root or >= parent — At root or >= parent

Next lesson: Extract

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies