Discussion :

[franklin626]

Bonsoir,

je travaille actuellement sur la notion de tas (ou "heap", "heapsort"). J'ai une procédure qui réalise une insertion dans ce tas en O(log n).
Insérer n éléments me coûte alors 0(n log n).
J'ai lu dans un ouvrage d'algorithmique qu'il est possible de construire un tas en 0(n) mais je ne trouve pas de ressources supplémentaires ou d'algorithme support sur le net.

Quelqu'un saurait-il m'aiguiller ?

D'avance, merci aux lecteurs de ce post !

[Furikawari]

Construire un tas en O(n) veut dire qu'on a un algo de tri en O(n)...
Heapsort est en O(n) sur un tas trié, mais en O(n log n) dans le cas général.

[franklin626]

je ne suis pas sûr de bien comprendre.

J'ai clairement lu qu'on peut "remplir" et uniquement remplir un tableau trié comme un tas, après avoir restreint sa taille, en O(n).

Il ne s'agit alors pas encore d'un tri, car pour ce faire, il faudra encore supprimer N fois.
Il se eut que je me trompe, mais je n'ai pas bien compris ce que tu disais.

[gasche]

Tu as raison, on peut construire un tas en O(n) mais le tri par tas reste en O(n log n). Cette méthode de construction bien connue est due à Floyd (1964) : tu parcours ton tableau de la fin vers le début, en "faisant descendre" chaque élément à sa bonne place dans le tas.

Tu peux trouver un exemple dans le premier pseudo-code donné par l'article wikipédia sur le tri par tas.

L'analyse de la complexité n'est cependant pas évidente, il faut faire le calcul.