Python Reference

Python HeapQ Use Cases and Time Complexity

An overview and guide to the Python heapq module

A look at the Python heapq library

Steve walks into the emergency room at 2pm with an intense stomach ache. At 2:01, Allen comes in with a severe cough. At 2:02, Shirley stumbles in with a knife wound in her side. Once the doctor is free, who should be seen first? Most of us would say that Shirley should be seen first. But how did we arrive at this conclusion?

This is called triaging. Triaging is the act of assigning priority to a queue. How would we write a program that could triage these? The algorithm details may be up to specific health protocols, but the underlying data structures would be the same — heaps or priority queues.

Priority queues allow you to prioritize something with multiple attributes based on one that you care about. Advanced priority queue setups allow you to sort based on more than one attribute. In most cases, priority queues are implemented with heaps. In Python, the heapq module is the Python heap queue library.

It’s not the only way to implement these data structures. The heapq library is just an easy way to implement these natively in Python. In this post, we’ll learn about that module. We will cover:

• Python heapq Module Introduction