Best online algorithm for a monotone priority queue that has equal amount of deletion and insertions

Question

I got an executor thread that is given jobs to execute at certain timestamp. So this means my problem is online.

While there are cases when the new job has a timestamp in the past, we can easily test for that and set the timestamp one millisecond into the future. So the series is monotone.

Currently, I got an array where I store the jobs, then every "tick" I sort the array and process the jobs whose timestamp are below the current time. This sounds bad so I want to improve it.

When inserting jobs I tend to have many which are recurrent jumps in time (timers), eg currenttime+250ms, and once I execute that job I insert another one for another 250ms into the future.

I have another set which are not recurrent, but are also a jump into the future, eg currenttime+576ms. A weird subset of these are very long jumps into the future, eg one day or more. Usually, its short jumps, at most 5 seconds.

I have another set which is aimed towards the very next loop and is also not recurrent, but every loop I end up generating many of these so they are always present, eg currenttime+1ms, I could always keep a separate array for these, if that makes the data structure for the rest faster

As I process them in order, I only need to pop() the top/bottom, and then remove it

As I eventually delete every insertion, I assume both operations should be fast

So, I need fast insert at any position with autosort probably, fast peek / select-min, fast pop / remove-min, search can be super slow so long as peek+pop are fast, and remove at arbitrary index other than min could also be super slow

I read on balanced binary trees and they seem fast but then I noticed their search and remove anywhere are logn so they are good "under all terrains" which is more than what I need, there are also priority queues of many types, so I wonder if theres anything even more optimized towards what I need

Answer 1

For say 100 items a priority queue will be just fast enough.

You could take an unsorted queue for anything far in the future. Set a “future time threshold” = now plus one hour; you don’t change this threshold usually. Everything with an execution time > threshold goes into that queue. Say ten seconds before the threshold time, you update the threshold time to current time plus one hour, then you iterate through the queue and move everything before the new threshold time into the “normal” queue. Efficiency doesn’t matter much because you do that once an hour. You don’t touch that queue except once shortly before the threshold time approaches.

Now you say you have a huge number of items with time set to current time + 0.25 seconds. Their times are all sorted. So you put all these into a separate queue, which is sorted not because you sort it, but because you append items in sorted order. The other items go into a priority queue. Now if you want the item with the earliest time, you just compare the first item in the priority queue and the sorted queue and take the earlier one.

Since you don’t want to check the time for your “far distant” items all the time, you add a task for that into the priority queue with time threshold minus ten seconds.

Summary: One priority queue, one accidentally sorted queue, and one far distant queue that you mostly ignore. Execution time for a priority queue grows with the logarithm of the queue size. So your "far away" items don't affect the size of the priority queue, the sorted items don't affect the size of the priority queue and are handled in constant time, and only the items near to the current time and with more or less random times increase the size of the priority queue.