Heap-based implementation
- Algorithms course
- Intermediate
- Lesson 42/80
- 4 min
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.
Practice Push
Write push(arr, val). Insert into min-heap. Print [0, 1, 2, 3] with arr = [1, 3, 2]; push(arr, 0); print(arr).
Starter code
def push(arr, val):
# Insert into min-heapSample 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)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 Push operation
arr.append(val)
sift_up(arr, len(arr) - ____)arr.append(val)
sift_up(arr, len(arr) - 1)Explanation: 1 is right.
2 Heap-based implementation: match the terms
| Term | Meaning |
|---|---|
Push |
Append + sift-up |
Pop |
Take root + sift-down |
Peek |
Read root |
Empty |
Error |
3 What is done after pop?
- Sift-up
- Nothing
- Sift-down Correct answer
- Rebuild
Explanation: Sift-down