Bonjour, je travaille sur un algorithme de classification ascendente hiérarchique (CAH). L'algo est assez simple :

on a un ensemble de point. A chaque point est associé un numéro.

On calcule les distances 2 à 2 et on récupère les 2 points pour lesquels la distance est minimale. Puis on crée un nouveau point, barycentre des 2 points sélectionnés. Ensuite on efface toutes les combinaisons de paire de points faisant intervenir au moins 1 des points sélectionnés et on recalcule toutes les distances entre le nouveau point et les points restant.

Je dois donc récupérer les 2 points qui minimisent la distance. J'ai donc fait une

multimap<double, pair<int, int> >

ou double est la distance et les 2 int sont les numéros des 2 points.

Que vaut-il mieux faire : utilisez une multimap ou bien une bête liste chainées dans laquelle je fais moi-même l'insertion par ordre croissant ?

Car je dois aussi effacer toutes les paires inutiles (car je supprime des points) et je dois aussi en insérer (toutes les paires faisant intervenir le nouveau point créé).

J'ai entendu dire que le point d'entrée de l'arbre (des multimap) était recalculé à chaque fois que l'on fait une insertion / suppression.

Je cherche à gagner du temps de calcul...

Merci d'avance