Aperçu des algorithmes de tri Tri par tas

Aperçu de l'algorithme de tri par tas

Apprenez la structure de données du tas et comment elle est utilisée pour le tri

Introduction

Le tas est une structure de données qui représente un tableau sous la forme d’un arbre binaire. Le tas impose les règles suivantes pour sa structure :

• Complétude. Chaque niveau du tas est complètement rempli d’éléments. Cependant, le dernier niveau peut être partiellement rempli d’éléments à partir de la gauche.
• Règle du tas. La valeur du nœud parent doit être inférieure ou égale aux valeurs de ses enfants. Si cette propriété est satisfaite, le tas est appelé min-heap. Il existe également une variation max-heap pour laquelle les valeurs des parents doivent être supérieures aux valeurs des enfants.

Des exemples et du code dans cet article seront fournis pour les tas min. Le flux de travail de l’algorithme pour les tas max ressemble beaucoup. Un exemple de min-heap est présenté ci-dessous.

• Vue d’ensemble des algorithmes de tri Quicksort
• Le Guide Ultime pour Entraîner BERT à partir de Zéro Préparer le Jeu de Données
• Comment évaluer les représentations

Le tas est généralement stocké sous la forme d’un tableau. Si un parent a l’indice i, alors les positions de ses enfants gauche et droit sont respectivement 2 * i + 1 et 2 * i + 2. Inversement, si un nœud non racine a l’indice i, alors le nœud parent a l’indice (i – 1) // 2. En suivant ce principe, nous obtenons la représentation sous forme de tableau du tas ci-dessus :

Opérations

Le tas prend en charge plusieurs opérations :

• Insertion d’un nœud
• Construction d’un tas à partir d’un tableau
• Extraction d’un nœud ayant la valeur minimale
• Tri

Étant donné que la structure de données du tas a plusieurs opérations, il est plus pratique de l’implémenter sous la forme d’une classe. Pour l’instant, nous allons implémenter ses bases. Après chaque opération, un extrait de code correspondant sera fourni.

• Le champ du tas stocke un tableau d’entrée sous la forme d’un tas (sera implémenté ultérieurement)
• La méthode _swap() prend deux indices du tableau et échange leurs valeurs.
• La méthode _number_of_children() retourne le nombre d’enfants qu’un nœud possède (0, 1 ou 2)

Insertion d’un nœud

Le nouvel élément du tas est inséré à la dernière position. Une telle insertion peut rompre la règle du tas si le nouvel élément est inférieur à la valeur du parent. Pour éviter ce problème, le nouveau nœud est propagé récursivement vers le haut jusqu’à ce qu’il ne viole pas la règle du tas. La procédure décrite est appelée heapify(up).

À partir de la figure ci-dessus, nous insérons un nœud avec la valeur 3.

• Après l’insertion, la règle du tas est violée, car 3 < 15 (parent). Nous échangeons les éléments 3 et 15.
• Maintenant, le nœud 3 a un nouveau parent qui a la valeur 7. Encore une fois, la règle du tas n’est pas satisfaite, car 3 < 7. En conséquence, nous échangeons 3 et 7.
• Le nœud 3 se trouve à l’indice 2 et a un parent avec la valeur 1. Comme 3 ≥ 1, la règle du tas est correcte. À ce stade, la procédure d’insertion se termine.

Déterminons la complexité temporelle pour l’insertion. Le pire des cas est possible lorsque le nouveau nœud doit être propagé du bas vers le niveau supérieur d’un arbre. Étant donné que la hauteur de tout arbre est logarithmique par rapport au nombre total de ses éléments N et que chaque comparaison prend un temps O(1), l’estimation finale donne un temps O(logN).

• La méthode insert() ajoute la valeur au tas, puis appelle la méthode pour le réorganiser.
• La méthode _heapify_up() invoque récursivement elle-même sur un nœud parent jusqu’à ce que la règle du tas soit respectée.

Construction d’un tas

Pour chaque élément d’un tableau d’entrée, une procédure d’insertion est appelée. C’est ainsi qu’un tas est construit.

En ce qui concerne la complexité, il peut sembler que la construction d’un tas nécessite O(N * logN) de temps car pour chacun des N éléments, nous appelons une fonction qui fonctionne en O(logN) temps. Cependant, il est possible d’améliorer cette estimation et de prouver mathématiquement que le temps total est O(N).

• Pour le tableau passé en paramètre de la méthode build(), le tas est construit grâce à des appels d’insertion.

Extraction d’un nœud avec la valeur minimale

Le nœud minimum se trouve en haut du tas. Nous extrayons le minimum et remplaçons le nœud du haut par le dernier nœud du tas. La règle du tas est violée, nous propageons donc cet élément vers le bas. L’algorithme est très similaire à celui que nous avons utilisé précédemment (lors de l’insertion, les éléments étaient propagés vers le haut) : à chaque étape, nous échangeons l’élément actuel avec un enfant qui a la valeur minimale. Cette procédure dure jusqu’à ce que la règle du tas ne soit plus violée ou que l’élément actuel n’ait pas d’enfant.

Sur la figure ci-dessus, le nœud avec la valeur 1 a été extrait et le dernier nœud avec la valeur 15 a pris sa place.

• Étant donné que le nœud 15 viole la règle du tas, nous l’échangeons avec son plus petit enfant qui est 3.
• Ensuite, le nœud 15 a les enfants 7 et 8 qui sont inférieurs. Encore une fois, nous échangeons 15 avec le plus petit enfant qui est 7.
• Après cela, 15 se trouve à l’indice 5 et n’a qu’un seul enfant qui est 20. Comme 15 ≤ 20, nous arrêtons la procédure de heapify.

Tout comme l’algorithme heapify dans la section d’insertion, celui-ci a la même asymptote et fonctionne en O(logN) temps.

Tri

Le tri est réalisé via l’extraction du nœud minimum. Tant que le tas n’est pas vide, nous appelons la fonction extract_min() et ajoutons chaque élément minimum à un nouveau tableau. Ainsi, le tableau sera composé d’éléments triés.

Étant donné que le tas contient N nœuds et que extract_min() fonctionne en O(logN), le temps total de tri est de O(N * logN).

Conclusion

Nous avons couvert les quatre principales opérations sur les tas. Pour trier un tableau en utilisant une structure de tas, il est nécessaire de construire d’abord un tas, puis d’appeler la méthode de tri dessus. La construction d’un tas nécessite un temps O(N) et le tri prend un temps O(N * logN), ce qui résulte finalement en une asymptote de O(N * logN) pour le tri par tas.

L’implémentation complète de la classe Heap est présentée ci-dessous.

Toutes les images, sauf indication contraire, sont de l’auteur.

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!