How to create queue of events in order by date

Question

I am trying to create a queue of events and I want to be able to insert and delete from the middle of the queue in constant time, something like this:

3446 --- 9493 --- 15969 --- 48381

where the number could be millis from now, or whatnot.

How could I insert an event between the 9493 and 15969 event?

I could use binary search to find the events in the queue with the desired times, but is there an easier way?

Answer 1

What you're looking for is called a priority queue:

https://en.wikipedia.org/wiki/Priority_queue

The typical way to implement one is to use a heap; you get O(log n) insert time and O(log n) delete time (for removing the highest priority item from the queue). Check the Wikipedia page for a list of other potential data structures, some of which have better amortized time.