In this reading, we will learn about the last new data structure of the quarter!
Consider if you were writing software for a hospital to manage the waiting list of patients. Your system should be able to add new patients in to the waiting list and remove a patient that should be served next; both of these operations should be as efficient as possible. Why not use a Queue
for this situation? Doesn't it efficiently implement add
and remove
(both in O(1)
time)?
Well, this problem is a bit different than ones we've seen before because in real life, we don't really care about who showed up at the hospital first, but rather who is in the most urgent need for help. If we were to use a plain old Queue
, we would be serving patients in a first-in-first-out (FIFO) manner; this means someone who stubbed their toe would be seen before someone with a life-threatening wound just because they showed up first, which does not seem right.
Instead, we would want a data structu