data-structures - 用于在 OCaml 中频繁重新安排队列的快速功能数据结构

Question

我的问题是为基于事件的模拟选择数据结构。

N 个 future 事件及其发生时间一起被维护。 N 是固定的或至少是有界的，范围从 10 到 10000。每个事件都有一个唯一的 ID，除了时间之外，原则上可以通过该 ID 检索它。

在循环中，会发生以下情况。删除并执行下一个发生的事件，并生成一个随机 future 时间的同类新事件来替换它。作为副作用，一些 (<10) 现有事件改变了它们的发生时间，需要重新安排。这些待重新安排的事件的 ID 是已知的，但不知道它们的发生时间。

我认为堆可以快速获取最低元素，但我还需要快速重新排序通过 ID 访问的任意元素。有 BatHeap哪个在 O(log N) 中查找元素和插入，但它似乎不允许索引访问？

我更喜欢持久结构(部分用于教育目的)，但如果只有可变结构运行速度快，我会使用它。

Answer 1

在第一次近似时，您可以使用堆或映射(堆具有 O(1) 优先删除而不是 O(log n)，但可能无法实现随机删除)与将 id 映射到时间的哈希表配对。映射结构不需要持久化，因为它可以从时间索引结构中轻松重建。