Summary - Priority queue

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.

Exercise Summary: push and pop

Write push(arr, val). Print 1 with arr = [2]; push(arr, 1); push(arr, 3); print(arr[0]).

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

Test yourself

Summary - Priority queue: match the terms

Push

Insert
Pop

Extract
Peek

O(1)
Application

Dijkstra

Min-heap root

In a min-heap the root is the ____

Show answer

In a min-heap the root is the smallest

What is the peek cost?
- O(1)
- O(n)
- O(n log n)
- O(log n)
Show answer

O(1) — O(1)

Next lesson: Project: Overview

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies