Forum Programmation.autre Algorithmie : les tas (heap)

Posté par  .
Étiquettes : aucune
0
1
sept.
2005
- Comment diviser un tas en deux tas de même cardinalité ? (en O(logn) dans le pire des cas et constant en espace)
- Comment fusionner un tas S1 et S2 de même cardinalité en un tas S (en O(logn) dans le pire des cas)

(sachant que le tas est stocké à l'aide de pointeurs père vers leurs 2 fils ...)

Toute documentation serait la bienvenue (liens, référence de livre, réponse directe, embryon de réponse, pistes à explorer, mots clefs se référants au sujet, etc).

Merci d'avance.

  • # Re : Algorithmie : les tas (heap)

    Posté par  . Évalué à 1.

    deja, je previens que je ne vais pas repondre a la question :/

    sans vouloir etre mechant, je ne comprends pas bien pourquoi tu veux absolument utiliser des tas, et des algo ayant une complexite imposee, sans connaitre justement ces algos repondant au probleme.

    en general, on essaye de faire un truc naif, et comme c'est trop long (en temps ou en taille), on utilise une structure de donnee particuliere car elle permet de gagner sur tel ou tel point qui pose probleme avec la solution naive.

    alors la, vouloir commencer avec une sdd donnee, et ne pas connaitre ou pas savoir sur quoi elle va faire gagner, me fait penser que le probleme est soit mal pense, soit les infos donnees sont volontairement reduite. dans les 2 cas, les reponses risquent souvent d'etre des rtfm & co :/

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.