首页 文章

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

提问于
浏览 次
2

我必须实现一个支持以下三个功能的数据结构 . 数据是两个双值的对（a，b），数据集中在特定区域 . 让我们说'a'的值在500-600范围内 .

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

  • 删除（双a） - 删除包含第一个元素的数据= a .

  • PrintData（int count） - 打印具有最大计数值的数据的值 . 根据data.first比较 Value .

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

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

c++ algorithm data-structures stl

2 回答

  • 2

    我建议使用2个二叉搜索树（BST） - 一个是从 a 到 b 的 Map （按 a 排序），另一个应按 b 排序 .

    第二个需要是自定义BST - 你需要让每个节点以root身份存储子树中节点数量的计数 - 这些计数可以在O（log n）中更新，并允许O（log n）查询以获得第k个最大元素 .

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

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

    所有提到的操作都应该采用O（log n） .

    Caching

    例如，如果您只查询前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 - 这将要求我们检查所有值以在删除后的查询期间找到所需的值，因此只有在那里它才会真正有用不是很多删除 .

    回复于
  • 2

    我会推荐indexed skip list . 这将为您提供O（log n）插入和删除，以及O（log n）访问第n个最大值（假设您按降序维护列表） .

    跳过列表并不比自 balancer 二叉树更难实现，并且在某些情况下可以提供更好的性能 . 非常值得考虑 .

    original skip list paper .

    回复于

相关问题