我的问题是为基于事件的模拟选择数据结构。
N 个未来事件连同它们的发生时间一起被维护。N 是固定的或至少是有界的，范围从 10 到可能 10000。每个事件都有一个唯一的 ID，除了时间之外，原则上可以通过该 ID 检索它。
在一个循环中，会发生以下情况。下一个发生的事件被移除并执行，并生成一个随机未来时间的同类新事件来替换它。作为副作用，一些 (<10) 现有事件改变了它们的发生时间，需要重新安排。这些要重新安排的事件的 ID 是已知的，但不知道它们的发生时间。
我认为堆可以快速获得最低元素，但我还需要快速重新排序通过 ID 访问的任意元素。有BatHeap在 O(log N) 中查找元素和插入，但似乎不允许索引访问？
我更喜欢持久结构（部分用于教育目的），但如果只有可变结构可以快速运行，我会使用它。
您需要一个优先级队列来解决您的问题，而对于优先级队列，堆是最好的选择。
如果你想要一个持久堆，你可以在 OCaml中实现一个Leftist 堆，用于你的教育目的。
但是，BatHeap 也可以满足您的需求，因为它是功能堆。
好的，我现在知道你想要a heap + map什么了。
你需要知道mapOCaml 中的操作是O(logN)因为功能的原因。您可以使用hashtbl，但它使用数组，它imperative不是持久方式或功能方式。
如果你想要一种纯函数式的方式，并且可以接受O(logN)，那么你需要有两种数据结构，一种是堆，另一种是映射。
在映射中，键是事件类型 id，值是该事件类型的堆。
但我想即使你发明了一个HeapMap东西，你仍然需要双倍空格，因为两种信息 (order of time和order of index) 都被维护了。
在第一个近似值上，您可以使用与将 ids 映射到时间的 Hashtable 配对的 Heap 或 Map（Heap 具有 O(1) 先删除而不是 O(log n)，但可能无法实现随机删除）。映射结构不需要是持久的，因为它可以从时间索引结构中轻松重建。