Summary - Priority queue
- Algorithms course
- Intermediate
- Lesson 44/80
- 4 min
Push tasks and pop the highest-priority one in a mini task.
Summary - Priority queue
Priority queue: highest/lowest priority first. Implemented with a heap: push O(log n), pop O(log n), peek O(1).
Foundation of Dijkstra, Huffman, task scheduler, A* search. Min-heap prioritizes smallest, max-heap largest.
Insert is much faster than a sorted array; extract much faster than an unsorted array.
Practice Summary: push and pop
Write push(arr, val). Print 1 with arr = [2]; push(arr, 1); push(arr, 3); print(arr[0]).
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 = [2]
push(arr, 1)
push(arr, 3)
print(arr[0])Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Priority queue: match the terms
| Term | Meaning |
|---|---|
Push |
Insert |
Pop |
Extract |
Peek |
O(1) |
Application |
Dijkstra |
2 Min-heap root
Question
In a min-heap the root is the ____
Answer
In a min-heap the root is the smallestExplanation: The root of a min-heap is the smallest element.
3 What is the peek cost?
- O(1) Correct answer
- O(n)
- O(n log n)
- O(log n)
Explanation: O(1)