Lookup structure for handling future events (time based)

Question

I am looking for an efficient data structure, that'll allow me to cue events ... that is, i will be having an app, where at any time in execution, it is possible, that an event will be raised for a future point in execution ... something like:

• t=20: in 420 seconds, A occurs
• t=25: in 13 seconds, B occurs
• t=27: in 735 seconds, C occurs
• ...

so i'd like to have a data structure, where i can put in any event in any time in the future and where i can get and (by doing so) remove all due events ... also, a plus would be, if i were able to remove an event from the datastructure (because it was canceled) ... not too important though, since i can simply flag it as cancelled ...

my first thought was, maybe to do some sort of tree, but i guess the removing-due-events part requires a lot of rebalancing ...

i am considering simply having an int hash, mapping timestamps to either null or stacks of events that are to occur at that point in time ... i think in scenarios, with a lot of events (possibly multiple every second - which is what i intend to work with), this actually isn't such a bad idea after all ...

so i am eager to hear your input ... :)

---

edit:

• to be more specific: i think n here is at about 100K-1M, and i guess i might be having about 1-100 events/second ...
• the t is of no special importance ... it is only to illustrate that a future event can be "enqueued" at any time ...

---

thanks

back2dos

Answer 1

I believe you're looking for a Priority Queue with the timestamp of when the event occurs being the priority (well, lower timestamps would be higher priority)

Just a little elucidation with your use cases:

... where i can put in any event in any time in the future...

You'd insert into the priority queue with insertWithPriority, using the timestamp of when the event occurs. This would be O(lgN)

... and where i can get and (by doing so) remove all due events ...

You'd repeatedly call getTop (gets event with the lowest timestamp) collecting all elements up to the time of interest.

... also, a plus would be, if i were able to remove an event from the datastructure (because it was canceled) ... not too important though, since i can simply flag it as cancelled ..

This would be possible, but would be O(lgN) due to rebalancing.

Answer 2

How big is N? How often do you have to insert & remove items, compared to everything else going on? If this is more than 10% of total execution time, and if N is typically more than 100 (say) maybe, maybe it's time to be concerned about big-O. I've seen programs with priority queues implemented with fancy container algorithms, allocating iterators, hash maps, heaps, etc. and spending all their time in creating and releasing abstract objects, where the median queue length was like three.

ADDED: OK, since N ~ 10^6, and the frequency is ~ 100hz, you probably want some sort of binary tree or heap with O(log(N)) insertion/removal time. If you're willing to devote 1% of CPU time to this, that is 10^6 microseconds * 1% / 100 = 10^2 microseconds / operation. That should not be at all difficult, because if typical search depth is 20, at ~50ns per comparison, that is ~1 microsecond to do the search. Just make sure to keep it simple, not getting all wrapped up in abstract datatypes. You shouldn't have to worry much about time spent in allocating/freeing tree nodes because you only allocate/free one node per operation. Rebalancing need not be done frequently, like maybe only after every 1000 operations. If you can collect your insertions in batches, and then insert them in random order, that may prevent the tree from getting too unbalanced. If many of your events are simultaneous, you could add a small amount of noise to the time code, to prevent parts of the tree from becoming more like a linear list.