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

Question

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

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

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

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

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

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

Answer 1

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

第二个需要是一个自定义的 BS​​T - 你需要让每个节点存储子树中的节点数，并将其作为根节点 - 这些计数可以在 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 以及 BST 映射 a 到 b - 这需要我们在删除后的查询期间检查所有值以找到所需的值，因此只有在没有大量删除的情况下才真正有益。