Summary - Heap
- Algorithms course
- Intermediate
- Lesson 40/80
- 4 min
Add items to a max-heap and print the root in a mini task.
Summary - Heap
Heap: complete binary tree, array representation. In a min-heap the root is smallest. Insert O(log n) (sift-up), extract O(log n) (sift-down).
Parent (i-1)//2, children 2i+1, 2i+2. Foundation of heap sort and priority queues.
Build heap O(n); all non-leaves are heapified.
Practice Summary: heap insert
Write heap_insert(arr, val). Append, sift_up. Print [0, 3, 1] with arr = [1, 3]; heap_insert(arr, 0); print(arr).
Starter code
def heap_insert(arr, val):
# Insert into 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 heap_insert(arr, val):
# Insert into heap
arr.append(val)
sift_up(arr, len(arr) - 1)
arr = [1, 3]
heap_insert(arr, 0)
print(arr)Expected output
[0, 3, 1]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Heap: match the terms
| Term | Meaning |
|---|---|
Min-heap |
Root smallest |
Sift-up |
Insert |
Sift-down |
Extract |
Build heap |
O(n) |
2 Parent
Question
parent = (i - 1) // ____
Answer
parent = (i - 1) // 2Explanation: 2 is right.
3 What is the heap build cost?
- O(n) Correct answer
- O(log n)
- O(n log n)
- O(1)
Explanation: O(n)