Priority queues

Sometimes the order things come out is neither "most recent" nor "oldest" but "most important". A priority queue always gives you the smallest value it holds, whatever order the values went in. Urgent orders first, cheapest option first, nearest deadline first.

You could keep a list and call min each time, but min looks at every item, and removing it shifts the rest. The standard library's heapq module keeps a list arranged so that the smallest item is always at position 0 and both adding and removing are fast.

import heapq

prices = []
heapq.heappush(prices, 40)
heapq.heappush(prices, 2.5)
heapq.heappush(prices, 25)
print(prices[0])

print(heapq.heappop(prices))
print(heapq.heappop(prices))
print(heapq.heappop(prices))

heappush adds a value. heappop removes and returns the smallest. prices[0] peeks at the smallest without removing it. Do not use append or sort on a list you are treating as a heap; only the heapq functions keep it arranged correctly.

If you print the list between pushes you will see it is not sorted. It has a special arrangement called a heap that only promises the smallest is first. That is enough.

Priorities with data attached

To attach information to a priority, push tuples. Python compares tuples one position at a time: the first values decide, and only if they are equal does it look at the second values, then the third. So (priority, item) is ordered by priority. Smaller numbers come out first; if you want "higher priority first", use negative numbers.

import heapq

orders = []
heapq.heappush(orders, (3, "bread"))
heapq.heappush(orders, (1, "wedding cake"))
heapq.heappush(orders, (2, "sandwiches"))

while orders:
    priority, item = heapq.heappop(orders)
    print(priority, item)

If two priorities tie, Python compares the second values, so the items must be comparable with each other. Strings and numbers are fine. When they are not, or when you want ties to come out in arrival order, push (priority, count, item) where count goes up by one with every push: the count breaks the tie and the item is never compared.

import heapq

orders = []
count = 0
for priority, item in [(1, "cake"), (1, "rolls"), (0, "bread")]:
    heapq.heappush(orders, (priority, count, item))
    count += 1

while orders:
    priority, count, item = heapq.heappop(orders)
    print(priority, item)

Starting from a list

heapify turns an existing list into a heap in place. nsmallest and nlargest give the k smallest or largest without emptying it.

import heapq

prices = [40, 25, 2.5, 60, 15]
heapq.heapify(prices)
print(prices)
print(prices[0])

print(heapq.nsmallest(2, prices))
print(heapq.nlargest(2, prices))

The second line of output shows that heapify rearranged the list: it is in heap order now, not the order you wrote. If you need the original order kept, heapify a copy.

Which one?

Comes out first	Structure	Operations
Most recently added	stack: a list	append, pop
Oldest	queue: a deque	append, popleft
Smallest	priority queue: heapq on a list	heappush, heappop

Try it

Next most urgent

orders is a list of (priority, name) tuples, lower number meaning more urgent, in no particular order. Write most_urgent(orders) that returns the name of the most urgent order without changing the list. The list has at least one order and no two orders share a priority.

most_urgent([(3, "bread"), (1, "wedding cake"), (2, "sandwiches")])  ->  "wedding cake"

import heapq

def most_urgent(orders):
    ...

Cheapest k

Write cheapest(prices, k) that returns the k smallest numbers in prices, smallest first. If k is larger than the list, return everything sorted; if k is 0, return an empty list. Do not change prices.

cheapest([40, 25, 2.5, 60, 15], 2)  ->  [2.5, 15]
cheapest([40, 25], 5)               ->  [25, 40]
cheapest([40, 25], 0)               ->  []

import heapq

def cheapest(prices, k):
    ...

Process by priority

orders is a list of (priority, name) tuples, lower meaning more urgent, with no two sharing a priority. Write in_priority_order(orders) that returns the names in the order they should be processed, most urgent first, using a heap: push them all, then pop until empty.

in_priority_order([(3, "bread"), (1, "wedding cake"), (2, "sandwiches")])
    ->  ["wedding cake", "sandwiches", "bread"]

import heapq

def in_priority_order(orders):
    heap = []
    for order in orders:
        ...
    result = []
    while heap:
        ...
    return result

Next: Practice.