Guide des tas en Python

Introduction

Imaginez un aéroport animé avec des vols qui décollent et atterrissent toutes les minutes. Tout comme les contrôleurs aériens priorisent les vols en fonction de l'urgence, les tas nous aident à gérer et à traiter les données en fonction de critères spécifiques, garantissant que l'élément de données le plus « urgent » ou « important » est toujours accessible en haut.

Dans ce guide, nous nous lancerons dans un voyage pour comprendre les tas à partir de la base. Nous commencerons par démystifier ce que sont les tas et leurs propriétés inhérentes. À partir de là, nous plongerons dans la propre implémentation des tas par Python, le heapq module et explorez son riche ensemble de fonctionnalités. Ainsi, si vous vous êtes déjà demandé comment gérer efficacement un ensemble dynamique de données où l'élément de priorité la plus élevée (ou la plus basse) est fréquemment nécessaire, vous allez vous régaler.

Qu'est-ce qu'un tas ?

La première chose que vous voudriez comprendre avant de vous lancer dans l’utilisation des tas est qu'est-ce qu'un tas. Un tas se démarque dans le monde des structures de données en tant que centrale arborescente, particulièrement compétente dans maintenir l'ordre et la hiérarchie. Bien qu’il puisse ressembler à un arbre binaire pour un œil non averti, les nuances de sa structure et de ses règles de gouvernance le distinguent clairement.

L'une des caractéristiques déterminantes d'un tas est sa nature en tant que arbre binaire complet. Cela signifie que chaque niveau de l'arbre, sauf peut-être le dernier, est entièrement rempli. Au sein de ce dernier niveau, les nœuds se peuplent de gauche à droite. Une telle structure garantit que les tas peuvent être représentés et manipulés efficacement à l'aide de tableaux ou de listes, la position de chaque élément dans le tableau reflétant son emplacement dans l'arborescence.

La véritable essence d’un tas réside cependant dans son commande. Dans un tas max, la valeur d'un nœud donné dépasse ou est égale aux valeurs de ses enfants, positionnant le plus grand élément juste à la racine. D'un autre côté, un tas minimum fonctionne sur le principe inverse : la valeur de tout nœud est inférieure ou égale aux valeurs de ses enfants, garantissant que le plus petit élément se trouve à la racine.

Au fur et à mesure que nous progressons, nous approfondirons la manière dont ces propriétés inhérentes aux tas permettent des opérations efficaces et comment les fonctionnalités de Python heapq Le module intègre de manière transparente des tas dans nos efforts de codage.

Caractéristiques et propriétés des tas

Les tas, avec leur structure et leurs principes d'ordonnancement uniques, présentent un ensemble de caractéristiques et de propriétés distinctes qui les rendent inestimables dans divers scénarios informatiques.

Avant tout, les tas sont intrinsèquement efficace. Leur structure arborescente, en particulier le format d'arbre binaire complet, garantit que les opérations telles que l'insertion et l'extraction d'éléments prioritaires (maximum ou minimum) peuvent être effectuées en temps logarithmique, généralement O (log n). Cette efficacité est une aubaine pour les algorithmes et les applications qui nécessitent un accès fréquent aux éléments prioritaires.

Une autre propriété notable des tas est leur efficacité de la mémoire. Étant donné que les tas peuvent être représentés à l’aide de tableaux ou de listes sans avoir besoin de pointeurs explicites vers des nœuds enfants ou parents, ils économisent de l’espace. La position de chaque élément dans le tableau correspond à son emplacement dans l'arborescence, permettant un parcours et une manipulation prévisibles et simples.

La propriété de classement des tas, qu'il s'agisse d'un tas maximum ou d'un tas min, garantit que la racine contient toujours l'élément de plus haute priorité. Cet ordre cohérent permet un accès rapide à l’élément prioritaire sans avoir à parcourir toute la structure.

De plus, des tas sont polyvalente. Bien que les tas binaires (dans lesquels chaque parent a au plus deux enfants) soient les plus courants, les tas peuvent être généralisés pour avoir plus de deux enfants, appelés tas d-aires. Cette flexibilité permet un réglage précis en fonction de cas d'utilisation spécifiques et d'exigences de performances.

Enfin, des tas sont auto-ajustable. Chaque fois que des éléments sont ajoutés ou supprimés, la structure se réorganise pour conserver ses propriétés. Cet équilibrage dynamique garantit que le tas reste optimisé pour ses opérations principales à tout moment.

À mesure que nous approfondirons l’implémentation et les applications pratiques de Python, le véritable potentiel des tas se dévoilera devant nous.

Types de tas

Tous les tas ne sont pas créés égaux. En fonction de leur ordre et de leurs propriétés structurelles, les tas peuvent être classés en différents types, chacun avec son propre ensemble d'applications et d'avantages. Les deux principales catégories sont tas max et les tas minimum.

La caractéristique la plus distinctive d'un tas max est que la valeur d'un nœud donné est supérieure ou égale aux valeurs de ses enfants. Cela garantit que le plus grand élément du tas réside toujours à la racine. Une telle structure est particulièrement utile lorsqu'il est nécessaire d'accéder fréquemment à l'élément maximum, comme dans certaines implémentations de files d'attente prioritaires.

La contrepartie du tas max, un tas minimum garantit que la valeur d'un nœud donné est inférieure ou égale aux valeurs de ses enfants. Cela positionne le plus petit élément du tas à la racine. Les tas min sont inestimables dans les scénarios où le moindre élément est primordial, comme dans les algorithmes traitant du traitement des données en temps réel.

Au-delà de ces catégories principales, les tas peuvent également être distingués en fonction de leur facteur de branchement :

Bien que les tas binaires soient les plus courants, chaque parent ayant au plus deux enfants, le concept de tas peut être étendu aux nœuds ayant plus de deux enfants. Dans un tas d-aire, chaque nœud a au plus d enfants. Cette variation peut être optimisée pour des scénarios spécifiques, comme diminuer la hauteur de l'arbre pour accélérer certaines opérations.

Tas binomial est un ensemble d'arbres binomiaux définis de manière récursive. Les tas binomiaux sont utilisés dans les implémentations de files d'attente prioritaires et offrent des opérations de fusion efficaces.

Nommé d'après la célèbre séquence de Fibonacci, le tas de Fibonacci offre des temps d'exécution mieux amortis pour de nombreuses opérations par rapport aux tas binaires ou binomiaux. Ils sont particulièrement utiles dans les algorithmes d'optimisation de réseau.

Implémentation du tas de Python – Le tas Module

Python propose un module intégré pour les opérations sur le tas : le heapq module. Ce module fournit un ensemble de fonctions liées au tas qui permettent aux développeurs de transformer des listes en tas et d'effectuer diverses opérations sur le tas sans avoir besoin d'une implémentation personnalisée. Plongeons dans les nuances de ce module et comment il vous apporte la puissance des tas.

Le heapq Le module ne fournit pas de type de données de tas distinct. Au lieu de cela, il propose des fonctions qui fonctionnent sur les listes Python classiques, en les transformant et en les traitant comme tas binaires.

Cette approche est à la fois économe en mémoire et s'intègre parfaitement aux structures de données existantes de Python.

Cela signifie que les tas sont représentés sous forme de listes in heapq. La beauté de cette représentation réside dans sa simplicité : le système d’index de liste de base zéro sert d’arbre binaire implicite. Pour tout élément donné à la position i, son:

• L'enfant de gauche est en position 2*i + 1
• L'enfant droit est en position 2*i + 2
• Le nœud parent est à la position (i-1)//2

Cette structure implicite garantit qu'il n'est pas nécessaire d'avoir une représentation arborescente binaire distincte basée sur les nœuds, ce qui rend les opérations simples et l'utilisation de la mémoire minimale.

Il est essentiel de noter que le heapq module crée des tas minimum par défaut. Cela signifie que le plus petit élément est toujours à la racine (ou à la première position de la liste). Si vous avez besoin d'un tas maximum, vous devrez inverser l'ordre en multipliant les éléments par -1 ou utilisez une fonction de comparaison personnalisée.

Python heapq Le module fournit une suite de fonctions qui permettent aux développeurs d'effectuer diverses opérations sur le tas sur les listes.

Dans les sections suivantes, nous approfondirons chacune de ces opérations fondamentales, en explorant leurs mécanismes et leurs cas d'utilisation.

Comment transformer une liste en tas

Le heapify() La fonction est le point de départ de nombreuses tâches liées au tas. Il prend un itérable (généralement une liste) et réorganise ses éléments sur place pour satisfaire les propriétés d'un tas min :

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Cela affichera une liste réorganisée qui représente un tas min valide :

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Comment ajouter un élément au tas

Le heappush() La fonction permet d'insérer un nouvel élément dans le tas tout en conservant les propriétés du tas :

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

L'exécution du code vous donnera une liste d'éléments conservant la propriété min tas :

[3, 5, 7]

Comment supprimer et renvoyer le plus petit élément du tas

Le heappop() La fonction extrait et renvoie le plus petit élément du tas (la racine dans un tas min). Après la suppression, cela garantit que la liste reste un tas valide :

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Cela affichera le plus petit élément et la liste restante :

1
[3, 7, 5, 9]

Ici, 1 est le plus petit élément du heap, et la liste restante a conservé la propriété tas, même après la suppression 1.

Comment pousser un nouvel élément et faire apparaître le plus petit élément

Le heappushpop() La fonction est une opération combinée qui pousse un nouvel élément sur le tas, puis affiche et renvoie le plus petit élément du tas :

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Cela produira 3, le plus petit élément, et imprimez le nouveau heap liste qui comprend désormais 4 tout en conservant la propriété du tas :

3
[4, 5, 7, 9]

Comment remplacer le plus petit élément et pousser un nouvel élément

Le heapreplace() la fonction fait apparaître le plus petit élément et pousse un nouvel élément sur le tas, le tout en une seule opération efficace :

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Cette imprime 1, le plus petit élément, et la liste en comprend désormais 4 et conserve la propriété tas :

1
[4, 5, 7, 9]

Trouver plusieurs extrêmes dans le tas de Python

nlargest(n, iterable[, key]) et les nsmallest(n, iterable[, key]) les fonctions sont conçues pour récupérer plusieurs éléments les plus grands ou les plus petits d’un itérable. Ils peuvent être plus efficaces que de trier l’intégralité de l’itérable lorsque vous n’avez besoin que de quelques valeurs extrêmes. Par exemple, supposons que vous ayez la liste suivante et que vous souhaitiez trouver les trois valeurs les plus petites et les trois valeurs les plus grandes dans la liste :

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Ici, nlargest() et les nsmallest() les fonctions peuvent être utiles :

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Cela vous donnera deux listes : l'une contient les trois plus grandes valeurs et l'autre contient les trois plus petites valeurs de la liste. data liste:

[9, 6, 5]
[1, 1, 2]

Comment créer votre tas personnalisé

Alors que Python heapq fournit un ensemble robuste d'outils pour travailler avec des tas, il existe des scénarios dans lesquels le comportement par défaut du tas min pourrait ne pas suffire. Que vous cherchiez à implémenter un tas maximum ou que vous ayez besoin d'un tas fonctionnant sur la base de fonctions de comparaison personnalisées, la création d'un tas personnalisé peut être la réponse. Voyons comment adapter les tas à des besoins spécifiques.

Implémentation d'un tas maximum en utilisant heapq

Par défaut, heapq crée des tas minimum. Cependant, avec une astuce simple, vous pouvez l'utiliser pour implémenter un tas maximum. L'idée est d'inverser l'ordre des éléments en les multipliant par -1 avant de les ajouter au tas :

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

Avec cette approche, le plus grand nombre (en termes de valeur absolue) devient le plus petit, ce qui permet heapq fonctions pour maintenir une structure de tas maximale.

Tas avec fonctions de comparaison personnalisées

Parfois, vous pourriez avoir besoin d’un tas qui ne se limite pas à comparer en fonction de l’ordre naturel des éléments. Par exemple, si vous travaillez avec des objets complexes ou si vous avez des critères de tri spécifiques, une fonction de comparaison personnalisée devient indispensable.

Pour y parvenir, vous pouvez envelopper des éléments dans une classe d'assistance qui remplace les opérateurs de comparaison :

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

Avec cette configuration, vous pouvez définir n'importe quelle fonction de comparaison personnalisée et l'utiliser avec le tas.

Conclusion

Les tas offrent des performances prévisibles pour de nombreuses opérations, ce qui en fait un choix fiable pour les tâches prioritaires. Cependant, il est essentiel de prendre en compte les exigences et caractéristiques spécifiques de l’application concernée. Dans certains cas, modifier l'implémentation du tas ou même opter pour des structures de données alternatives peut donner de meilleures performances dans le monde réel.

Les tas, comme nous l'avons parcouru, sont plus qu'une simple structure de données. Ils représentent une confluence d’efficacité, de structure et d’adaptabilité. De leurs propriétés fondamentales à leur implémentation dans Python heapq module, les tas offrent une solution robuste à une myriade de défis informatiques, en particulier ceux centrés sur la priorité.

• Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
• PlatoData.Network Ai générative verticale. Autonomisez-vous. Accéder ici.
• PlatoAiStream. Intelligence Web3. Connaissance Amplifiée. Accéder ici.
• PlatonESG. Carbone, Technologie propre, Énergie, Environnement, Solaire, La gestion des déchets. Accéder ici.
• PlatoHealth. Veille biotechnologique et essais cliniques. Accéder ici.
• La source: https://stackabuse.com/guide-to-heaps-in-python/