Push and pop
- Algorithms course
- Intermediate
- Lesson 43/80
- 4 min
push and pop respect priority.
Push and pop
In a priority queue push and pop rely on the heap's sift-up and sift-down. Push adds a new element and sifts up.
Pop removes the root, moves the last element to the root and sifts down. Both are O(log n).
These operations are used to pick the highest-priority task in a scheduler.
Applications
The priority queue is used in many places. In Dijkstra to pick the nearest node. In Huffman coding to merge the least frequent characters.
In a task scheduler to run the highest-priority process. In A* search to pick the lowest-cost path.
The heap is the core of these applications.
Practice Pop
Write pop(arr). Remove the root from a min-heap. Print 1 with arr = [1, 3, 2, 5]; print(pop(arr)).
Starter code
def pop(arr):
# Remove rootSample solution
def sift_down(arr, n, i):
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] < arr[smallest]:
smallest = left
if right < n and arr[right] < arr[smallest]:
smallest = right
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
sift_down(arr, n, smallest)
def pop(arr):
# Remove root
result = arr[0]
arr[0] = arr[-1]
arr.pop()
if arr:
sift_down(arr, len(arr), 0)
return result
arr = [1, 3, 2, 5]
print(pop(arr))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Push and pop: match the terms
| Term | Meaning |
|---|---|
Push |
Sift-up |
Pop |
Sift-down |
Cost |
O(log n) |
Root |
Smallest |
2 What does Dijkstra use the priority queue for?
- Farthest node
- Random node
- First node
- Nearest node Correct answer
Explanation: Nearest node
3 Pop result
result = arr[____]result = arr[0]Explanation: 0 is right.