Discussion :

[deeal]

salut
je voudrais faire une insertion dicho , mais avec reinsertion
(ie: si l'element existe deja on l'insere quand meme, car pour moi la comparaison c'est juste un deuxieme element de la liste
[[element1,priorite1],[element2,priorite2]]
donc on peut avoir deux element distinct avec des priorites egales
donc il faut le reinserer
merci de donner quelque idees

[Trap D]

Excuse moi, mais pourrais-tu reformuler la question, avec des exemples, car je n'ai rien compris

[Nemerle]

+1

[deeal]

est-ce que vous connaissez l'insertion dichotomique??
si oui quand vous voulez inserer un element et que l'element existe , on l'insere pas, donc moi je veux l'inserer, mais je ne sais pas comment faire pour otimiser
[7,6,6,6,6,6,5,3,1,0] :notre chaine, et je veux inserer mon 6
ma premiere boucle sorte qu'on a trouve le 6 a l'indice 4 , comment je fais pour inserer l'element au debut apres le 7 en optimisant

[kaisse]

est-ce que vous connaissez l'insertion dichotomique??
si oui quand vous voulez inserer un element et que l'element existe , on l'insere pas, donc moi je veux l'inserer, mais je ne sais pas comment faire pour otimiser
[7,6,6,6,6,6,5,3,1,0] :notre chaine, et je veux inserer mon 6
ma premiere boucle sorte qu'on a trouve le 6 a l'indice 4 , comment je fais pour inserer l'element au debut apres le 7 en optimisant

Typiquement, si tu veux conserver l'insertion dichomotique, je ne vois pas 36 solutions: tu fais ton truc habituel, typiquement là tu prends le 6 du milieur, et quand tu rencontre la même valeur de priorité, tu parcours depuis où tu es à l'envers, jusqu'à rencontrer un élément supérieur (ici 7). Forcément dans le pire des cas la complexité de ton insertion devient linéaire (au lieu de logarithmique). Mais bon, si tu as trop de redondances des indices de priorité, c'est surement que celle-ci a été définie. Typiquement, pour 3 objets de même priorité, tu ne perds rien.

[deeal]

oui je vais comme cela ça me semble bien, si il y'a beaucoup de chemin avec la meme priorite ça veut dire qu'il y'a un probleme dans la definition des priorites entrees par l'utilisateurs