Algorithme de tri par tas (avec code dans Python et C++)
Sarah Chen
Qu’est-ce que l’algorithme de tri par tas ?
Heap Sort est l’un des algorithmes de tri les plus populaires et les plus rapides. Il est construit sur la structure complète des données de l'arborescence binaire. Nous rechercherons l'élément maximum et le placerons en haut pour le tas maximum. Nous allons le mettre sur le nœud parent de l'arbre binaire.
Disons qu'un tableau est donné, données = [10,5, 7, 9, 4, 11, 45, 17, 60].
Dans le tableau, si le i-ième (i=0,1,2,3 …) index est un nœud parent alors, (2i+1) et (2i+2) seront les enfants gauche et droit. La création d'un arbre binaire complet avec ce tableau ressemblera à ceci :
Nous effectuerons le processus heapify du début à la fin du tableau. Initialement, si nous convertissons le tableau en arbre, il ressemblera à celui ci-dessus. Nous pouvons voir qu'il ne conserve aucune propriété de tas (min-heap ou max tas). Nous obtiendrons le tableau trié en effectuant le processus heapify pour tous les nœuds.
Application du tri par tas
Voici une utilisation de l'algorithme de tri par tas :
- La construction de « files d’attente prioritaires » nécessite un tri par tas. Parce que le tri par tas maintient l'élément trié après chaque insertion.
- La structure de données du tas est efficace pour trouver le kth le plus grand élément d'un tableau donné.
- Le noyau Linux utilise le tri par tas par défaut algorithme de tri car il a une complexité spatiale O (1).
Créer un tri par tas avec un exemple
Ici, nous allons construire un tas maximum à partir de l'arbre binaire complet suivant.
Les nœuds feuilles sont 17, 60, 4, 11 et 45. Ils n'ont aucun nœud enfant. C'est pourquoi ce sont des nœuds feuilles. Nous allons donc démarrer la méthode heapify à partir de leur nœud parent. Voici les étapes :
Étape 1) Sélectionnez le sous-arbre le plus à gauche. Si les nœuds enfants sont plus grands, échangez le nœud parent avec le nœud enfant.
Ici, le nœud parent est 9. Et les nœuds enfants sont 17 et 60. Comme 60 est le plus grand, 60 et 9 seront échangés pour maintenir le tas max.
Étape 2) Désormais, le sous-arbre le plus à gauche est regroupé. Le nœud parent suivant est 7. Ce parent a deux nœuds enfants et le plus grand est 45. Ainsi, 45 et 7 seront échangés.
Étape 3) Les nœuds 60 et 4 ont le nœud parent 5. Comme « 5 » est plus petit que le nœud enfant 60, il sera interverti.
Étape 4) Désormais, le nœud 5 a le nœud enfant 17,9. Cela ne maintient pas la propriété max tas. Ainsi, 5 sera remplacé par 17.
Étape 5) Le nœud 10 sera remplacé par le nœud 60, puis par le nœud 17. Le processus ressemblera à ce qui suit.
Étape 6) Jusqu'à l'étape 5, nous avons créé le tas maximum. Chaque nœud parent est plus grand que ses nœuds enfants. Le nœud racine a la valeur maximale (60).
Remarque: Pour créer le tableau trié, nous devons remplacer le nœud de valeur maximale par son successeur.
Ce processus est appelé "extraire max». Comme 60 est le nœud max, nous allons fixer sa position au 0ème index et créer le tas sans nœud 60.
Étape 7) Lorsque 60 est supprimé, la valeur maximale suivante est 45. Nous allons refaire le processus « Extraire Max » à partir du nœud 45.
Cette fois, nous obtiendrons 45 et remplacerons le nœud racine par son successeur 17.
Nous devons performer »Extraire maximum» jusqu'à ce que tous les éléments soient triés.
Après avoir effectué ces étapes jusqu'à ce que nous extrayions toutes les valeurs maximales, nous obtiendrons le tableau suivant.
Qu’est-ce que le tas binaire ?
Un tas binaire est une sorte de tas complet arbre binaire Structure de données. Dans ce type de structure arborescente, le nœud parent est soit plus grand, soit plus petit que les nœuds enfants. Si le nœud parent est plus petit, alors le tas est appelé « Min Heap » et si le nœud parent est plus grand, le tas est appelé « Max Heap ».
Voici des exemples de tas min et max.
Dans la figure ci-dessus, si vous remarquez le « Min Heap », le nœud parent est toujours plus petit que ses nœuds enfants. En tête de l’arbre, on retrouve la plus petite valeur 10.
De même, pour le « Max Heap », le nœud parent est toujours plus grand que les nœuds enfants. L'élément maximum est présent au nœud principal du « Max Heap ».
Qu’est-ce que « Heapify » ?
« Heapify » est le principe du tas qui assure la position du nœud. Dans Heapify, un tas maximum maintient toujours une relation avec le parent et l'enfant, et ce nœud parent sera plus grand que les nœuds enfants.
Par exemple, si un nouveau nœud est ajouté, nous devons remodeler le tas. Cependant, nous devrons peut-être modifier ou échanger les nœuds ou réorganiser le tableau. Ce processus de remodelage d'un tas est appelé « heapify ».
Voici un exemple du fonctionnement de heapify :
Voici les étapes pour heapify :
Étape 1) Ajout du nœud 65 comme enfant droit du nœud 60.
Étape 2) Vérifiez si le nœud nouvellement ajouté est supérieur au parent.
Étape 3) Comme il est supérieur au nœud parent, nous avons échangé le bon enfant avec son parent.
Comment construire le tas
Avant de construire le tas ou de regrouper un arbre, nous devons savoir comment nous allons le stocker. Comme le tas est un arbre binaire complet, il est préférable d'utiliser un tableau pour contenir les données du tas.
Disons qu'un tableau contient un total de n éléments. Si le « i » ème index est un nœud parent, alors le nœud de gauche sera à l’index (2i+1), et le nœud de droite sera à l'index (2i+2). Nous supposons que l'index du tableau commence à 0.
En utilisant cela, stockons un tas maximum dans un tableau semblable à celui-ci :
L'algorithme heapify conserve la propriété tas. Si le parent n'a pas la valeur extrême (inférieure ou supérieure), il sera échangé avec le nœud enfant le plus extrême.
Voici les étapes pour regrouper un tas maximum :
Étape 1) Commencez par le nœud feuille.
Étape 2) Trouvez le maximum entre le parent et les enfants.
Étape 3) Échangez les nœuds si le nœud enfant a une valeur supérieure à celle du parent.
Étape 4) Montez d'un niveau.
Étape 5) Suivez les étapes 2,3,4 jusqu'à ce que nous atteignions l'index 0 ou trions l'arbre entier.
Voici le pseudo-code pour heapify récursif (tas max) :
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
Pseudo-code pour le tri par tas
Voici le pseudo-code de l'algorithme de tri par tas :
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
Exemple de code de tri de tas dans C++
#include <iostream>
using namespace std;
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void heapify(int numbers[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && numbers[left] < numbers[largest])
{
largest = left;
}
if (right < n && numbers[right] < numbers[largest])
{
largest = right;
}
if (largest != i)
{
//uncomment the following line to see details in output
//cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
swap(numbers[i], numbers[largest]);
heapify(numbers, n, largest);
}
}
void heapSort(int numbers[], int n)
{
for (int i = n/2 - 1; i >= 0; i--)
{
heapify(numbers, n, i);
//uncomment the following line to see details in output
//cout<<"Heapify:\t";
//display(numbers,n);
}
for (int i = n - 1; i >= 0; i--)
{
swap(numbers[0], numbers[i]);
heapify(numbers, i, 0);
}
}
int main()
{
int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
int size = sizeof(numbers) / sizeof(numbers[0]);
cout<<"Initial Array:\t";
display(numbers,size);
heapSort(numbers, size);
cout<<"Sorted Array (descending order):\t";
display(numbers, size);
}
Sortie :
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
Exemple de code de tri de tas dans Python
def display(arr):
for i in range(len(arr)):
print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
largest = left
if right < n and numbers[right] < numbers[largest]:
largest = right
if largest != i:
numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
for i in range(n //2,-1,-1):
heapify(items, n, i) for i in range(n - 1, -1, -1):
items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
Sortie :
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Analyse de la complexité temporelle et spatiale du tri par tas
Il existe une complexité temporelle et une complexité spatiale que nous pouvons analyser pour le tri par tas. Pour la complexité temporelle, nous avons les cas suivants :
- Meilleur cas
- Cas moyen
- Pire cas
Le tas est implémenté sur un arbre binaire complet. Ainsi, au niveau inférieur de l’arbre binaire, il y aura le nombre maximum de nœuds. Si le niveau inférieur a n nœuds, alors le niveau supérieur aura n/2 nœuds.
Dans cet exemple, le niveau 3 comporte quatre éléments, le niveau 2 comporte deux éléments et le niveau 1 comporte un élément. S'il y a un nombre total de n éléments, la hauteur ou le niveau total sera Historique2(n). Ainsi, l’insertion d’un seul élément peut prendre un maximum de Log(n) itérations.
Lorsque nous voulons prendre la valeur maximale du tas, nous prenons simplement le nœud racine. Là encore, exécutez le heapify. Chaque tas prend Historique2(n) temps. L’extraction du maximum prend un temps O(1).
Meilleur cas de complexité temporelle pour l'algorithme de tri par tas
Lorsque tous les éléments sont déjà triés dans le tableau, il faudra O(n) temps pour construire le tas. Parce que si la liste est triée, l'insertion d'un élément prendra le temps constant O(1).
Ainsi, il faudra O(n) temps pour créer un tas maximum ou un tas min dans le meilleur des cas.
Complexité du temps moyen d'un cas pour l'algorithme de tri par tas
L'insertion d'un élément ou l'extraction d'un maximum coûte du temps O(log(n)). Ainsi, la complexité temporelle moyenne des cas pour l’algorithme de tri par tas est O(n log(n)).
Dans le pire des cas, complexité temporelle pour l'algorithme de tri par tas
Semblable au cas moyen, dans le pire des cas, nous pourrions effectuer n fois un tas. Chaque heapify coûtera du temps O(log(n)). Ainsi, la complexité temporelle dans le pire des cas sera O(n log(n)).
Complexité spatiale pour l'algorithme de tri par tas
Le tri par tas est un algorithme conçu sur place. Cela signifie qu'aucune mémoire supplémentaire ou temporaire n'est nécessaire pour effectuer la tâche. Si nous voyons l'implémentation, nous remarquerons que nous avons utilisé swap() pour effectuer l'échange des nœuds. Aucune autre liste ou tableau n'était nécessaire. Ainsi, la complexité spatiale est O(1).
