Push and pop

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.

Exercise Pop

Write pop(arr). Remove the root from a min-heap. Print 1 with arr = [1, 3, 2, 5]; print(pop(arr)).

Show example 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))

Test yourself

Push and pop: match the terms

Push

Sift-up
Pop

Sift-down
Cost

O(log n)
Root

Smallest
What does Dijkstra use the priority queue for?
- Farthest node
- Random node
- First node
- Nearest node
Show answer

Nearest node — Nearest node
Pop result
```
result = arr[____]
```
Show answer
```
result = arr[0]
```

Next lesson: Summary - Priority queue

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies