用于按键操作删除和搜索的有效数据结构
我有100组A对象，每组对应一个查询点Qi，1 <= i <= 100。
class A {
int id;
int distance;
float x;
float y;
}
在我的算法的每次迭代中，我选择一个查询点 Qi 并从相应的集合中提取具有最小距离值的对象。然后，我必须在所有 100 个集合中找到这个特定对象，使用其 id 进行搜索，并删除所有这些对象。
如果我对每组对象使用堆，则使用 MIN(distance) 提取对象会很便宜。但是，我将无法在使用 id 搜索的其他堆中找到相同的对象，因为堆是按照距离值组织的。此外，更新堆的成本很高。
我考虑过的另一个选择是为每组使用 map 。这种方式通过 id 进行搜索（查找操作）是很便宜的。然而，提取最小值的元素需要线性时间（它必须检查映射中的每个元素）。
是否有任何我可以使用的数据结构对我需要的操作都有效？
- extract_min(distance)
- find(id)
提前致谢！
I have 100 sets of A objects, each set corresponding to a query point Qi, 1 <= i <= 100.
class A {
int id;
int distance;
float x;
float y;
}
In each iteration of my algorithm, I select one query point Qi and extract from the corresponding set the object having the minimum distance value. Then, I have to find this specific object in all 100 sets, searching with its id, and remove all those objects.
If I use a heap for each set of objects, it is cheap to extract the object with MIN(distance). However, I will not be able to find the same object in other heaps searching with the id, because the heap is organized with the distance value. Further, updating the heap is expensive.
Another option I have considered is using a map<id, (distance, x, y)> for each set. This way searching (find operation) by id is cheap. However, extracting the element with the minimum value takes linear time (it has to examine every element in the map).
Is there any data structure that I could use that is efficient for both the operations I need?
- extract_min(distance)
- find(id)
Thanks in advance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
std::map或boost::multi_indexstd::maporboost::multi_index您可以使用树形图。
You could use a tree map.
一种简单的方法是每个数据集有两个地图。第一个包含按 id 排序的所有数据项。第二个是一个
multimap并将距离映射到 id，这样您就可以轻松找出最小距离对应的 id。这个将按距离排序，以使查找最小值变得便宜（因为它将使用距离作为键）。如果您知道距离始终是唯一的，则可以使用map而不是multimap。One simple approach is to have two maps for each data set. The first one contains all the data items sorted by id. The second would be a
multimapand map distance to id so that you could easily figure out what id the lowest distance corresponds to. This one would be ordered by distance to make finding the min cheap (since it would use distance as the key). You could usemapinstead ofmultimapif you know that distances will always be unique.除了包含地图之外
楼上很多人都建议你
可以取代你的最小堆
具有一个结构
运行时复杂度是恒定的
对于提取分钟。您当前的版本
运行时复杂度为 O(log_2(n))
提取分钟
由于您的距离范围是
小，你可以使用“拨号数组”
算法。键就像“计数排序”。
因为您可能有不止一件商品
一个数组项，但你不关心
等值物品的顺序，您可以使用
作为数组项的双向链表
数据类型。安德鲁·戈德堡和塔里安论文
关于更快的 Dijkstra 算法
更详细地讨论这一点。
In addition to ncluding a map as
suggested by many above, you
could replace your minimum heap
with a structure that has a
runtime complexity that is constant
for extract min. Your current version
has runtime complexity of O(log_2(n))
for extract min.
Since the range of your distances is
small, you could use a "Dial array"
algorithm. The keys are like "counting sort".
Because you may have more than one item in
an array item, but you don't care about the
order of equal value items, you would use
a doubly linked list as the array's item
data type. The Andrew Goldberg and Tarjan papers
regarding faster Dijkstra's algorithms
dicuss this in more detail.