1

我正在寻找一种适当有效的存储结构来处理以随机顺序到达但必须以指定顺序从堆栈中处理和/或删除的数据。

为了更清楚地说明这一点：

每个项目 x 都有一个索引 i，一个时间戳 t，并按如下方式处理（假设存储结构已填充）。

repeat
  1) Process (remove) the item with the smallest time stamp.
  2) Add new items (0 or more).
  3) Remove (0 or more) items (referenced by their index).
until false

保证每个项目都有唯一的时间戳和索引。但是，在步骤 1) 完成之前，无法预测在步骤 2) 中将添加多少项，或者在步骤 3) 中删除多少项，直到在算法的每个循环中完成步骤 1) 和 2)。无法预测传入项目的时间戳分布（除了新的时间戳将在“未来”中），并且可能随时间变化 - 即可能有一堆随机分布的时间戳，然后是一堆时间戳更大的时间戳（或小于）列表中剩余的任何项目。任何时候都会有最大数量的元素等待处理，但这可能相当大~10^6-10^8，

如果我在步骤 2) 中将每个项目添加到链接排序列表中，则步骤 1) 是 O(0)，但步骤 2) 是 O(n)。如果我使用二叉树，那么步骤 1) 仍然是 O(1)，现在步骤 2) 最初是 O(log n)，但是如果时间戳没有很好地分布，树可能会很快变得不平衡，这会减慢步骤 2)显着下降（如果我不定期重新平衡树，最终不会比 O(n) 好）。

我的猜测是，如果重新平衡以正确的时间间隔完成，那么具有定期重新平衡的二叉树应该提供 O(log n) ，但我认为这类问题已经得到很好的解决，所以有人可以指导我找到合适的参考或给我一些建议，以帮助我避免重新发明轮子。

4

1 回答 1

4

使用数据结构堆，您可以在 O(logN) 中轻松完成所有操作。

http://en.wikipedia.org/wiki/Heap_(data_structure)

堆以时间戳为键。并且您将需要一个额外的数组（或字典）来存储对 Q=（item.Index，堆中项目的位置）。

由于它是一个堆，因此操作 1) 和 2) 将花费 O(logN) 处理每个项目。

对于操作 3)，您需要从堆中删除随机项。幸运的是，正如这里提到的，这很容易。因为 item.index 不是它在堆中的实际位置，所以您需要上面提到的字典 Q ，通过 O(1) 中的 item.Index 查找项目在堆中的位置（用于哈希映射） ，否则寻找该位置将花费 O(N)。并且由于项目的位置在操作（包括操作 1 和 2）期间可能会发生变化，因此请记住每次在堆中移动项目时更改 Q 中的值。

正如有人提到的优先队列，我将在这里添加更多内容。

优先级队列是一种抽象数据类型，具有一些抽象接口。而且这些界面不包括常识中的“删除随机项目”。

堆是一种数据结构。

优先级队列可以用堆来实现。但是堆可以支持比优先级队列更多的操作。

于 2012-08-02T03:46:57.493 回答