← Back to context

Comment by pncnmnp

1 day ago

Hi! Author here. I agree that I should have explicitly stated the word "priority queues" since it is an ADT people can directly relate to. I will add it in. However, it is simply not true that I did not describe how a priority queue-based solution works.

I have described it in the "Timer Modules" section:

> A natural iteration of this approach is to store timers in an ordered list (also known as timer queues). In this scheme, instead of storing the time interval, an absolute timestamp is stored. The timer identifier and its corresponding timestamp that expires the earliest is stored at the head of the queue. Similarly, the second earliest timer is stored after the earliest, and so on, in ascending order. After every unit, only the head of the queue is compared with the current timestamp. If the timer has expired, we dequeue the list and compare the next element. We repeat this until all the expired timers have been dequeued, and we run their expiry processing routines.

And then, I go on to talk about its runtime.

Truth be told, this is a chapter for my book on data structures and algorithms that I think are interesting and obscure enough that not many people talk about them. Its goal is not widespread practicality, but rather a fun deep dive into some topics.