2

我有 100 组 A 对象，每组对应一个查询点 Qi 1 <= i <= 100，.

class A {
    int id;
    int distance;
    float x;
    float y;
}

在我的算法的每次迭代中，我选择一个查询点 Qi 并从相应的集合中提取具有最小距离值的对象。然后，我必须在所有 100 个集合中找到这个特定对象，使用它的 id 进行搜索，然后删除所有这些对象。

如果我为每组对象使用一个堆，那么使用MIN(distance). 但是，我将无法在使用 id 搜索的其他堆中找到相同的对象，因为堆是使用距离值组织的。此外，更新堆是昂贵的。

我考虑过的另一个选择是map<id, (distance, x, y)>为每组使用一个。这种按 id 搜索（查找操作）的方式很便宜。但是，提取具有最小值的元素需要线性时间（它必须检查地图中的每个元素）。

是否有任何我可以使用的对我需要的操作都有效的数据结构？

  • extract_min（距离）
  • 查找（ID）

提前致谢！

4

4 回答 4

0

您可以使用树状图。

于 2010-11-15T16:48:45.943 回答
0

std::map或者boost::multi_index

于 2010-11-15T16:50:54.530 回答
0

一种简单的方法是为每个数据集设置两个映射。第一个包含按 id 排序的所有数据项。第二个是 amultimap并映射到 id 的距离，以便您可以轻松找出最低距离对应的 id。这将按距离排序，以使找到最小值便宜（因为它将使用距离作为键）。如果您知道距离始终是唯一的，则可以使用map而不是。multimap

于 2010-11-15T18:10:42.353 回答
0

除了包含上述许多人建议的映射之外，您还可以将最小堆替换为具有运行时复杂性的结构，该结构对于提取最小值是恒定的。您当前的版本对于提取 min 具有 O(log_2(n)) 的运行时复杂度。
由于您的距离范围很小，您可以使用“拨号阵列”算法。键就像“计数排序”。因为您可能在一个数组项中有多个项，但您不关心等值项的顺序，您将使用双向链表作为数组的项数据类型。Andrew Goldberg 和 Tarjan 关于更快 Dijkstra 算法的论文更详细地讨论了这一点。

于 2016-06-11T08:34:40.287 回答