Différence entre sort, make_heap et sort_heap

Bonjour,

j'ai beau chercher dans différentes docs pour comparer les variantes d'explications, je ne trouve aucune explication claire des différences entre :

- std::sort< T , std::greater > // je précise pour garder le même sens entre les tris
- std::make_heap
- std::sort_heap

A priori, les trois fonctions vont faire exactement la même chose si par exemple on les applique à un vecteur, du moins au regard du résultat.
Quand je regarde l'implementation, je ne comprends pas tout, mais visiblement le code à l'air différent entre chaque.

Un de mes collegues a supposé que seul le sort n'allouait aucune mémoire, est-ce le cas?

J'aimerai savoir quelles sont les différences entre ces fonctions pour savoir si je peux optimiser un algorithme dans lequel j'ai une heap sous forme d'un vecteur que je dois donc trier au besoin.
Si il y a une différence de performance du a une différence d'algorithme, j'aimerai la connaitre.

Merci de votre attention.

Elles ne font pas la même chose.

make_heap crée une heap, qui n'est pas une structure triée, mais une représentation à plat d'un arbre binaire où chaque élément est plus petit que son père.

sort_heap crée une structure triée à partir d'une heap (le résultat n'est donc plus une heap).

sort trie simplement une structure.

La heap a l'air d'être appropriée si on va au cours du temps continuellement ajouter des données dans le désordre, puis les retirer la plus grand en premier, au fur et à mesure.

Pour avoir des données triées, un sort semble plus approprié.

Je comprends bien la différence des termes, mais vu que je fournis un vector, quelle est la différence entre une heap et un vector trié du plus grand au plus petit?


Dans mon cas, c'est une implementation de A*. Au départ j'utilisais une priority_queue et ça marchait très bien. Le problème c'est le controle de la mémoire qui semble impossible avec la priority_queue. Donc j'ai remplacé par un vector, et donc je dois faire des tris quand ya eu un ajout dans le vector.
Vu que c'est dans la boucle de recherche, ça doit être rapide.
Sachant tout cela, tu me conseilles toujours juste sort ?

dit autrement.

1. sort : trie les element du vector
2. make_heap : créé un arbre binaire où chaque élément est plus petit que son père => non trié
3. sort_heap : transforme un heap en un ensemble trié. Il faut donc que ton vertor soit sous forme de heap

Si tu veut avoir accé qu'à l'élément le plus grand (ou autre critère si tu passe un predicat) et que tu enlève tes élément dans l'ordre de grandeur. Tu n'est pas obligé de les trier. Le heap peu suffire.
Ainsi :

1. tu créé un heap avec ton vector. Normalement, le premier élément est toujours le plus grand
2. pour ajouter un élément :
   
   • tu ajoute ton element à la fin de ton vector
   • tu applique push_heap
3. pour elever le plus grand element :
   
   • tu applique pop_heap

Pour plus de détails, voir l'excellent article d'un certain r0d: http://r0d.developpez.com/articles/algos-stl/

:aie:

;)

Citation:

---

Envoyé par r0d

Pour plus de détails, voir l'excellent article d'un certain r0d: http://r0d.developpez.com/articles/algos-stl/

:aie:

;)

---

t'es fort parrain.
Je savais pas que tu l'avais ajouté

j'oublié :
Comment virée des valeur d'un heap :
1- tu vire les valeurs que tu veut du vector
2- tu fait make_heap