c++ - 支持各种操作的数据结构的实现

Question

我必须实现一个支持以下三个功能的数据结构。数据是两个 double 值的对(a,b)，并且数据集中在特定区域。假设“a”的值在 500-600 范围内。

1. Insert(double a, double b) - 在数据结构中插入数据，一对(double,double)。如果该对的第一个元素已存在，则将其第二个元素更新为新值。

2. Delete(double a) - 删除包含第一个元素 = a 的数据。

3. PrintData(int count) - 打印具有第 count 个最大值的数据的值。根据data.first来比较数值。

输入文件包含一系列的Insert、Delete和PrintData操作。目前，我已经使用STL-Map将数据结构实现为高度平衡二叉搜索树，但速度不够快。

是否有任何其他实现比 Map 更快。 我们可以使用缓存来存储最常见的 PrintData 查询。

Answer 1

我推荐 2 种二叉搜索树 (BST) - 一种是从 a 到 b 的映射(按 a 排序)，另一个应按 b 排序。

第二个需要是自定义 BST - 您需要让每个节点存储以它为根的子树中的节点数计数 - 这些计数可以在 O(log n) 中更新，并且将允许 O(log n) 查询获取第 k 大元素。

进行插入时，您只需首先在第一个 BST 中查找 b 的值，然后从第二个 BST 中删除该值，然后更新第一个并将新值插入到第二个中。

对于删除，您只需在第一个 BST 中查找 b 的值(并删除该对)，然后从第二个 BST 中删除该值。

所有提到的操作都应该花费 O(log n)。

缓存

例如，如果您只想查询前 10 个元素，则可以维护另一个仅包含这 10 个元素的 BST(或者甚至只是一个可选排序的数组，因为只有 10 个元素)，我们将然后查询而不是上面的第二个 BST。

插入时，如果值大于最小的，也插入到该结构中，并删除最小的。

删除时，我们需要查找下一个最大值并将其插入到小 BST 中。虽然这也可以延迟完成 - 删除时，只需将其从 BST 中删除 - 不要再次将其填充到 10。查询时，如果这个BST中有足够的元素，就用这个来查找，否则就找到大BST中所有需要填满这个BST的值，然后再查询。

这将导致最好情况下的 O(1) 查询(最坏情况下为 O(log n))，而其他操作仍为 O(log n)。

尽管增加的复杂性可能不值得 - O(log n) 相当快，即使对于很大的 n 也是如此。

基于这个想法，我们只能拥有这个小的 BST 以及将 a 映射到 b 的 BST - 这需要我们在删除后的查询过程中检查所有值以找到所需的值，因此只有在没有大量删除的情况下才真正有用。