Fast functional data structure for queueing with frequent rescheduling in OCaml

Question

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.

Answer 1

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.

Answer 2

You need a priority queue for your problem and for priority queue, heap is the best way to go.

If you want a persistent heap, you can implement a Leftist heap in OCaml, for your educational purpose.

However, BatHeap can also meet your need as it is functional heap.

---

Ok, I know what you wish a heap + map thing now.

You need to know that the operations of map in OCaml is O(logN) because of functional reason. you can use hashtbl, but it uses array which is imperative, not persistent way or functional way.

If you want a pure functional way, and can accept O(logN), then you need to have two datastructures, one is heap and the other is map.

In the map, the key is the event type id, and the value is the heap for that event type.

But I guess even if you invent a HeapMap thing, you need anyway double spaces as two kind of information (order of time and order of index) are maintained.