Algorithme de tri de multisets

Question

Je cherche un algorithme (de préférence en C/C++/Java ou similaire) pour trier un multiset. En explorant Internet, je suis arrivé à la conclusion que je devrais être capable de le faire en O (n log h). Avec h étant le nombre d'éléments distincts et n le nombre total d'éléments. Je n'ai cependant pas pu trouver un algorithme qui utilise le fait qu'un multiset puisse contenir des éléments répétés pour trier plus rapidement.

Cordialement!

Answer 1

Utilisez un arbre binaire équilibré.

Lors de l'insertion, si vous essayez d'insérer un élément déjà existant, au lieu de l'insérer, mettez à jour un nombre dans le noeud.

À la fin, effectuez une traversée dans l'ordre. Le nombre vous indique combien de fois un noeud est répété.