Tas

Heap est une structure arborescente spéciale dans laquelle chaque nœud parent est inférieur ou égal à son nœud enfant. Il s'agit alors d'un tas minimal. Si chaque nœud parent est supérieur ou égal à son nœud enfant, il s'agit d'un tas maximum. Il est très utile pour mettre en œuvre des files d'attente prioritaires où l'élément de la file d'attente ayant un poids plus élevé est traité en priorité.

Une discussion détaillée sur les tas est disponible sur notre site web ici. Veuillez l'étudier en premier si vous êtes novice en matière de structure de données heap. Dans ce chapitre, nous allons voir l'implémentation de la structure de données heap en utilisant Python.

Créer un tas

Un tas est créé en utilisant la bibliothèque intégrée de Python appelée heapq. Cette bibliothèque possède les fonctions nécessaires pour effectuer diverses opérations sur la structure de données du tas. Vous trouverez ci-dessous une liste de ces fonctions.

• heapify : Cette fonction convertit une liste régulière en un tas. Dans le tas résultant, le plus petit élément est poussé à la position d'index 0. Mais le reste des éléments de données ne sont pas nécessairement triés.
• heappush : Cette fonction ajoute un élément au tas sans modifier le tas actuel.
• heappop : Cette fonction retourne le plus petit élément de données du tas.
• heapreplace : Cette fonction remplace le plus petit élément de données par une nouvelle valeur fournie dans la fonction.

Création d'un tas

Un tas est créé en utilisant simplement une liste d'éléments avec la fonction heapify. Dans l'exemple ci-dessous, nous fournissons une liste d'éléments et la fonction heapify réorganise les éléments en plaçant le plus petit élément en première position.

Exemple