DAA - Méthode d'insertion

Pour insérer un élément dans un tas, le nouvel élément est initialement ajouté à la fin du tas comme dernier élément du tableau.

Après avoir inséré cet élément, la propriété de tas peut être violée, par conséquent la propriété de tas est réparée en comparant l'élément ajouté avec son parent et en déplaçant l'élément ajouté vers le haut d'un niveau, en échangeant des positions avec le parent. Ce processus s'appellepercolation up.

La comparaison est répétée jusqu'à ce que le parent soit plus grand ou égal à l'élément percolateur.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Une analyse

Au départ, un élément est ajouté à la fin du tableau. S'il viole la propriété du tas, l'élément est échangé avec son parent. La hauteur de l'arbre estlog n. Maximumlog n nombre d’opérations à effectuer.

Par conséquent, la complexité de cette fonction est O(log n).

Exemple

Considérons un tas max, comme indiqué ci-dessous, où un nouvel élément 5 doit être ajouté.

Initialement, 55 seront ajoutés à la fin de ce tableau.

Après l'insertion, il viole la propriété du tas. Par conséquent, l'élément doit échanger avec son parent. Après l'échange, le tas ressemble à ce qui suit.

Là encore, l'élément viole la propriété de heap. Par conséquent, il est échangé avec son parent.

Maintenant, nous devons nous arrêter.