Heap-based implementation

A heap-backed priority queue gives O(log n) ops.

Push and pop

Push: append the element, sift-up. O(log n).

Pop: save the root, move the last element to the root, sift-down, return the old root. O(log n).

These two operations form the basic interface of a priority queue. Thanks to the heap both are efficient and balanced.

Pop detail

Pop: first save result = arr[0]. Then arr[0] = arr[-1], arr.pop() (remove last). Then sift_down(arr, n, 0).

If the heap has one element just arr.pop(). Pop on an empty heap raises an error.

After pop the heap property is preserved; the next smallest comes to the root.

Exercise Push

Write push(arr, val). Insert into min-heap. Print [0, 1, 2, 3] with arr = [1, 3, 2]; push(arr, 0); print(arr).

Show example solution

def sift_up(arr, i):
    while i > 0:
        parent = (i - 1) // 2
        if arr[i] < arr[parent]:
            arr[i], arr[parent] = arr[parent], arr[i]
            i = parent
        else:
            break
def push(arr, val):
    # Insert into min-heap
    arr.append(val)
    sift_up(arr, len(arr) - 1)
arr = [1, 3, 2]
push(arr, 0)
print(arr)

Test yourself

Push operation

arr.append(val)
sift_up(arr, len(arr) - ____)

Show answer

arr.append(val)
sift_up(arr, len(arr) - 1)

Heap-based implementation: match the terms

Push

Append + sift-up
Pop

Take root + sift-down
Peek

Read root
Empty

Error
What is done after pop?
- Sift-up
- Nothing
- Sift-down
- Rebuild
Show answer

Sift-down — Sift-down

Next lesson: Push and pop

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies