Lesson 9 of 14

Heaps and Priority

You want to handle the task with the nearest deadline while new tasks keep arriving. Instead of sorting everything after each arrival, use a structure that quickly retrieves the next item to process.

Priority queues and heaps

A priority queue is an abstract data type that removes the highest-priority item. A binary heap is a common implementation.

• Shape: A complete binary tree. Every level is full except possibly the last, which fills from left to right.
• Min-heap rule: Each parent is no greater than its children. The minimum is at the root.
• Max-heap rule: Each parent is no smaller than its children, placing the maximum at the root.

A heap is not a fully sorted array. Siblings need not be ordered. The second array position need not hold the second-smallest value.

Store the tree in an array

With the root at index 0, node i has children at 2*i+1 and 2*i+2. A non-root node’s parent is at (i-1)//2. The complete shape lets positions express relationships without separate links.

Insertion adds at the end and moves the item upward while comparing it with its parent. Removing the minimum moves the last item to the root, then moves it downward against its children. Each operation takes O(log n). Inspecting the minimum without removing it takes O(1).

Retrieve tasks by deadline

import heapq

jobs = []
heapq.heappush(jobs, (3, "backup"))
heapq.heappush(jobs, (1, "reply"))
heapq.heappush(jobs, (2, "review"))

while jobs:
    print(heapq.heappop(jobs)[1])

Smaller numbers go first, so the output is reply, review, then backup. Tuples compare their first values first. Equal priorities fall back to comparing task names. To preserve arrival order for ties, put an increasing arrival number in the second position.

Check your understanding

What order results from repeatedly calling heappop until a min-heap is empty? Is reading its array from beginning to end equivalent?

Python documentation: heapq