Que fait heap push et comment ajoute-t-il un élément à la heap?

Heap push — c’est une opération d’ajout d’un nouvel élément dans la structure de données « tas » (heap), qui maintient les propriétés du tas (par exemple, minimum ou maximum).

Comment se déroule l’ajout :

1. Le nouvel élément est placé à la fin du tableau représentant le tas.
2. Ensuite, l’opération de « remontée » (sift-up ou bubble-up) est effectuée : l’élément est comparé à son parent, et si la propriété du tas est violée (par exemple, dans un min-heap, si l’élément est plus petit que son parent), les éléments sont échangés.
3. Ce processus est répété jusqu’à ce que l’élément soit à la bonne position, restaurant les propriétés du tas.

Ainsi, heap push assure l’ajout d’un élément tout en conservant l’ordre du tas, ce qui permet d’extraire efficacement l’élément minimum ou maximum.

Exemple en Python avec le module heapq :

import heapq

heap = [1, 3, 5, 7]
heapq.heapify(heap)  # Transforme la liste en tas

heapq.heappush(heap, 2)  # Ajoute l’élément 2
print(heap)  # Tas avec ordre conservé

En conséquence, l’élément 2 sera ajouté et « sifonné » vers le haut pour préserver les propriétés du min-heap.