My problem is to select a data structure for an event-based simulation.
A number N of future events are maintained together with their time of occurrence. N is fixed or at least bounded, ranging from 10 to maybe 10000. Each event has a unique ID by which it can be retrieved in principle, in addition to the time.
In a loop, the following happens. The next-occuring event is removed and executed, and a new event of the same kind for a random future time is generated to replace it. As a side effect, a few (<10) existing events change their time of occurrence and need to get rescheduled. The IDs of these to-be-rescheduled events are known but not their times of occurrence.
I was thinking a heap would be good to get the lowest element quickly but I also need quick reordering of arbitrary elements which are accessed by ID. There is BatHeap which does finding elements and insertion in O(log N), but it seems not to allow indexed access?
I would prefer a persistent structure (partly for educational purposes) but if only a mutable structure works fast, i'll use that.
On first approximation, you can use a Heap or Map (Heap has O(1) remove-first instead of O(log n), but may not implement random removal) paired to a Hashtable that maps ids to times. The mapping structure needs not be persistent as it can be trivially rebuilt from the time-indexed structure.