bac*_*dos 4 language-agnostic performance advanced-queuing data-structures
我正在寻找一个有效的数据结构,这将允许我提示事件...也就是说,我将有一个应用程序,在任何时候执行,有可能,一个事件将被提出以便将来执行点...类似于:
所以我想拥有一个数据结构,我可以在任何时间在任何时间放入任何时间,我可以获得和(通过这样做)删除所有应有的事件...另外,如果加上将是,如果我能够从数据结构中删除一个事件(因为它已被取消)...虽然不太重要,因为我可以简单地将其标记为已取消...
我的第一个想法是,也许要做某种树,但我想删除 - 因事件部分需要大量的再平衡......
我正在考虑简单地使用int哈希,将时间戳映射到null或在那个时间点发生的事件堆栈...我认为在场景中,有很多事件(可能每秒多次 - 这就是我打算工作),毕竟这实际上并不是一个坏主意......
所以我渴望听到你的意见...... :)
编辑:
谢谢
back2dos
Fal*_*ina 10
我相信你正在寻找一个优先级队列,其中包含事件发生时的时间戳作为优先级(嗯,较低的时间戳将是更高的优先级)
只是对您的用例进行一点阐述:
......我可以在任何时间将任何时间放入......
您将使用insertWithPriority插入优先级队列,使用事件发生时的时间戳.这将是O(lgN)
......以及我可以获得的地方(通过这样做)删除所有应有的事件......
您将反复调用getTop(获取具有最低时间戳的事件)收集所有元素,直到感兴趣的时间.
...如果我能够从数据结构中删除一个事件(因为它已被取消),那么也是一个加号......虽然不太重要,因为我可以简单地将其标记为已取消..
这是可能的,但由于重新平衡将是O(lgN).