100 セットの A オブジェクトがあり、各セットはクエリ ポイント Qi, に対応しています1 <= i <= 100。
class A {
int id;
int distance;
float x;
float y;
}
アルゴリズムの反復ごとに、1 つのクエリ ポイント Qi を選択し、対応するセットから最小距離値を持つオブジェクトを抽出します。次に、100 セットすべてからこの特定のオブジェクトを見つけ、その ID で検索し、それらのオブジェクトをすべて削除する必要があります。
オブジェクトのセットごとにヒープを使用すると、オブジェクトを抽出するのにコストがかかりませんMIN(distance)。ただし、ヒープは距離値で編成されているため、id で検索しても他のヒープで同じオブジェクトを見つけることができません。さらに、ヒープの更新にはコストがかかります。
私が検討した別のオプションは、map<id, (distance, x, y)>for each セットを使用することです。このように ID による検索 (find 操作) は安価です。ただし、最小値を持つ要素を抽出するには線形時間がかかります (マップ内のすべての要素を調べる必要があります)。
必要な両方の操作に効率的な、使用できるデータ構造はありますか?
- extract_min(距離)
- 検索 (ID)
前もって感謝します！