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

Question

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

1. 插入(双a，双b) -在数据结构中插入数据，一对(双，双)。如果该对的第一个元素已经存在，则将其第二个元素更新为新值。
2. 删除(Double a) -删除包含第一个元素= a的数据。
3. PrintData(int计数)-打印具有计数最大值的数据的值.根据data.first值进行比较。

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

还有其他比Map更快的实现吗？我们可以使用缓存来存储最常见的PrintData查询。

Answer 1

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

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

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

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

所有提到的操作都应该采用O(log )。

缓存

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

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

删除时，我们需要查找下一个最大值并将其插入到小型BST中。虽然这也可以懒洋洋地完成--当移除时，只需将其从BST中移除--不要再填充10次。当查询时，如果这个BST中有足够的元素，我们可以使用这个元素来查找，否则我们会在BST中找到填充这个BST所需的所有值，然后进行查询。

这将导致最佳情况O(1)查询(最坏情况O(log n))，而其他操作仍然是O(log n)。

虽然增加的复杂性可能不值得- O(log )非常快，即使对于一个大的n。

基于这个想法，我们只能使用这个小的BST以及BST映射a到b --这将要求我们检查所有的值，以便在删除后的查询过程中找到所需的值，所以只有在没有大量的删除时才能真正受益。