Discussion :

[evans]

Bonjour,

J'essaie d'effectuer la construction d'un "heap" à partir de deux "heaps" qui contiennent M et N éléments respectivement.

Mon problème est que j'essaie de respecter la complexité O(lg(M + N)) pour mon algorithme.

Est-ce que vous avez une suggestion sur la manière de construire mes "heaps" ou de les fusionner qui me permettrait d'avoir la complexité ci-dessus ?

Merci

[PRomu@ld]

Regarde du coté des tas binomiaux

http://en.wikipedia.org/wiki/Binomial_heap

[evans]

Bonjour,

Merci pour l'info !! J'aurais cru qu'il aurait été possible de le faire avec des monceaux "normal", mais je vois bien que ce serait de l'ordre de O(n).

Merci,

[PRomu@ld]

Avec un tas binomial toutes les opérations s'effectuent en O( log n ), de plus, la mise en place de cette structure est relativement simple.

Si tu as le moindre problème pour l'implémenter, n'hésites pas à poser des questions.