Effective data structure for both deleteMin and search by key operations

Question

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!

Answer 1

std::map or boost::multi_index