Structure de données efficace à la fois pour deleteMin et la recherche par opérations de touches

Question

J'ai 100 ensembles d'objets A, chaque ensemble correspondant à un point de requête Qi, 1 <= i <= 100.

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

Dans chaque itération de l'algorithme ma, je sélectionne un point d'interrogation Qi et extrait de l'ensemble de l'objet ayant la valeur de distance minimale correspondante. Ensuite, je dois trouver cet objet spécifique dans tous les 100 ensembles, en cherchant avec son identifiant, et supprimer tous ces objets.

Si j'utilise un tas pour chaque ensemble d'objets, il est bon marché d'extraire l'objet avec MIN(distance). Cependant, je ne serai pas capable de trouver le même objet dans d'autres tas en cherchant avec l'identifiant, car le tas est organisé avec la valeur de distance. De plus, la mise à jour du tas est coûteuse.

Une autre option que j'ai considérée est l'utilisation d'un map<id, (distance, x, y)> pour chaque ensemble. De cette façon, la recherche (trouver l'opération) par ID est bon marché. Cependant, extraire l'élément avec la valeur minimale prend un temps linéaire (il doit examiner chaque élément de la carte).

Y a-t-il une structure de données que je pourrais utiliser pour les opérations dont j'ai besoin?

• extract_min (distance)
• find (id)

Merci à l'avance!

Answer 1

std::map ou boost::multi_index

Answer 2

Vous pouvez utiliser une arborescence.

Answer 3

Une approche simple est d'avoir deux cartes pour chaque ensemble de données. Le premier contient tous les éléments de données triés par id. La deuxième serait un multimap et la distance de la carte à l'ID de sorte que vous puissiez facilement déterminer quel ID correspond à la distance la plus basse. Celui-ci serait ordonné par distance pour faire trouver le minimum bon marché (puisqu'il utiliserait la distance comme clé). Vous pouvez utiliser map au lieu de multimap si vous savez que les distances seront toujours uniques.

Answer 4

En plus de ncluding une carte comme suggéré par beaucoup plus haut, vous pourrait remplacer votre tas minimum avec une structure qui a une complexité d'exécution qui est constante pour l'extrait min. Votre version actuelle a une complexité d'exécution de O (log_2 (n)) pour l'extrait min.
Étant donné que la plage de vos distances est petit, vous pouvez utiliser un algorithme "Dial array" . Les clés sont comme "genre de comptage". Étant donné que vous pouvez avoir plus d'un élément dans un élément de tableau, mais vous ne vous souciez pas de l'ordre d'articles de valeur égale, vous utilisez une liste doublement liée en tant que type de données de tableau. Les documents Andrew Goldberg et Tarjan concernant les algorithmes plus rapides de Dijkstra en discuter plus en détail.