Python - tas

Le tas est une arborescence spéciale dans laquelle chaque nœud parent est inférieur ou égal à son nœud enfant. Ensuite, cela s'appelle un tas min. Si chaque nœud parent est supérieur ou égal à son nœud enfant, il est appelé un tas max. Il est très utile d'implémenter des files d'attente prioritaires où l'élément de file d'attente avec un poids plus élevé reçoit plus de priorité dans le traitement. Une discussion détaillée sur les tas est disponible sur notre site Web ici. Veuillez d'abord l'étudier si vous débutez dans la structure de données. Dans ce chapitre, nous verrons l'implémentation de la structure de données de tas en utilisant python.

Créer un tas

Un tas est créé en utilisant la bibliothèque intégrée de python nommée heapq. Cette bibliothèque a les fonctions appropriées pour effectuer diverses opérations sur la structure de données du tas. Voici 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 renvoie 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éer 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 amenant le plus petit élément à la première position.

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[1, 3, 5, 78, 21, 45]

Insertion dans le tas

L'insertion d'un élément de données dans un tas ajoute toujours l'élément au dernier index. Mais vous pouvez appliquer à nouveau la fonction heapify pour amener l'élément nouvellement ajouté au premier index uniquement s'il est le plus petit en valeur. Dans l'exemple ci-dessous, nous insérons le chiffre 8.

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

Suppression du tas

Vous pouvez supprimer l'élément au premier index en utilisant cette fonction. Dans l'exemple ci-dessous, la fonction supprimera toujours l'élément à la position d'index 1.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

Remplacement dans un tas

La fonction heapreplace supprime toujours le plus petit élément du tas et insère le nouvel élément entrant à un endroit non fixé par aucun ordre.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Replace an element
heapq.heapreplace(H,6)
print(H)

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]