Paul's Python CoursePPC

Priority queues

Not met yet

A priority queue hands out the most urgent thing first, whatever order things arrived in. With heapq, push tuples with the priority first: tuples compare item by item, so the lowest priority number comes out first. When two priorities tie, Python compares the next item along, so put an arrival count second, (priority, arrival, item), to keep ties first come, first served and never compare the items themselves. heapq only does smallest first; for biggest first, push the negative.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks heapq hands back items with the same priority in the order they were pushed, when the tuple's next item decides.
  • Thinks heapq hands back the largest item first.
  • Thinks two tuples with the same first item are treated as equal, so the rest of the tuple is never compared.
  • Thinks pushing the negative of the priority also reverses the order of ties between the other items in the tuple.

Where it comes up