logo

TechCodeview

Tri par tas – Tutoriels sur les structures de données et les algorithmes

Tri en tas est une technique de tri par comparaison basée sur Tas binaire Structure de données. C'est semblable au tri par sélection où nous trouvons d’abord l’élément minimum et plaçons l’élément minimum au début. Répétez le même processus pour les éléments restants.

Algorithme de tri en tas

Pour résoudre le problème, suivez l'idée ci-dessous :



vlc télécharger des vidéos youtube

Convertissez d'abord le tableau en structure de données de tas à l'aide de heapify, puis supprimez un par un le nœud racine du tas Max et remplacez-le par le dernier nœud du tas, puis tasez la racine du tas. Répétez ce processus jusqu'à ce que la taille du tas soit supérieure à 1.

  • Construisez un tas à partir du tableau d’entrée donné.
  • Répétez les étapes suivantes jusqu'à ce que le tas ne contienne qu'un seul élément :
    • Échangez l'élément racine du tas (qui est le plus grand élément) avec le dernier élément du tas.
    • Supprimez le dernier élément du tas (qui est maintenant dans la bonne position).
    • Regroupez les éléments restants du tas.
  • Le tableau trié est obtenu en inversant l'ordre des éléments dans le tableau d'entrée.
Problème recommandé Veuillez d'abord le résoudre par la PRATIQUE, avant de passer à la solution Résoudre le problème

Fonctionnement détaillé du tri par tas

Pour comprendre plus clairement le tri par tas, prenons un tableau non trié et essayons de le trier à l'aide du tri par tas.
Considérez le tableau : arr[] = {4, 10, 3, 5, 1}.

Construire un arbre binaire complet : Construisez un arbre binaire complet à partir du tableau.



Algorithme de tri par tas | Construire un arbre binaire complet

Transformer en tas maximum : Après cela, la tâche consiste à construire un arbre à partir de ce tableau non trié et à essayer de le convertir en tas maximum.

  • Pour transformer un tas en max-heap, le nœud parent doit toujours être supérieur ou égal aux nœuds enfants
    • Ici, dans cet exemple, en tant que nœud parent 4 est plus petit que le nœud enfant dix, ainsi, échangez-les pour créer un tas maximum.
  • Maintenant, 4 comme un parent est plus petit que l'enfant 5 , échangez donc à nouveau les deux et le tas et le tableau résultants devraient ressembler à ceci :

Algorithme de tri par tas | Arbre binaire construit par Max Heapify



Effectuez un tri par tas : Supprimez l'élément maximum à chaque étape (c'est-à-dire, déplacez-le vers la position finale et supprimez-le), puis considérez les éléments restants et transformez-le en un tas maximum.

  • Supprimer l'élément racine (dix) du tas maximum. Afin de supprimer ce nœud, essayez de l'échanger avec le dernier nœud, c'est-à-dire (1). Après avoir supprimé l'élément racine, regroupez-le à nouveau pour le convertir en tas maximum.
    • Le tas et le tableau résultants devraient ressembler à ceci :

Algorithme de tri par tas | Supprimer le maximum de la racine et max heapify

formes normales
  • Répétez les étapes ci-dessus et cela ressemblera à ceci :

Algorithme de tri par tas | Supprimer le maximum suivant de la racine et du tas max

  • Maintenant, supprimez à nouveau la racine (c'est-à-dire 3) et effectuez heapify.

Algorithme de tri par tas | Répéter l'étape précédente

  • Désormais, lorsque la racine est à nouveau supprimée, elle est triée. et le tableau trié ressemblera à arr[] = {1, 3, 4, 5, 10} .

Algorithme de tri par tas | Tableau trié final

Implémentation du tri par tas

C++ 
// C++ program for implementation of Heap Sort #include  using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) {  // Initialize largest as root  int largest = i;  // left = 2*i + 1  int l = 2 * i + 1;  // right = 2*i + 2  int r = 2 * i + 2;  // If left child is larger than root  if (l < N && arr[l]>arr[le plus grand]) le plus grand = l;  // Si l'enfant de droite est plus grand que le plus grand // jusqu'à présent si (r< N && arr[r]>arr[le plus grand]) le plus grand = r;  // Si le plus grand n'est pas racine if (largest != i) { swap(arr[i], arr[largest]);  // Heapify récursivement // le sous-arbre affecté heapify(arr, N, plus grand);  } } // Fonction principale pour effectuer le tri par tas void heapSort(int arr[], int N) { // Construire un tas (réorganiser le tableau) pour (int i = N / 2 - 1; i>= 0; i--) tasifier(arr, N, je);  // Extrait un par un un élément // du tas pour (int i = N - 1; i> 0; i--) { // Déplace la racine actuelle vers la fin du swap(arr[0], arr[i]);  // appelle max heapify sur le tas réduit heapify(arr, i, 0);  } } // Une fonction utilitaire pour imprimer un tableau de taille n void printArray(int arr[], int N) { for (int i = 0; i< N; ++i)  cout << arr[i] << ' ';  cout << '
'; } // Driver's code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function call  heapSort(arr, N);  cout << 'Sorted array is 
';  printArray(arr, N); }>
C 
// Heap Sort in C #include  // Function to swap the position of two elements void swap(int* a, int* b) {  int temp = *a;  *a = *b;  *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) {  // Find largest among root,  // left child and right child  // Initialize largest as root  int largest = i;  // left = 2*i + 1  int left = 2 * i + 1;  // right = 2*i + 2  int right = 2 * i + 2;  // If left child is larger than root  if (left < N && arr[left]>arr[le plus grand]) le plus grand = gauche ;  // Si l'enfant de droite est plus grand que le plus grand // jusqu'à présent si (droite< N && arr[right]>arr[le plus grand]) le plus grand = à droite ;  // Échangez et continuez à accumuler // si la racine n'est pas la plus grande // Si la plus grande n'est pas la racine if (largest != i) { swap(&arr[i], &arr[largest]);  // Heapify récursivement // le sous-arbre affecté heapify(arr, N, plus grand);  } } // Fonction principale pour effectuer le tri par tas void heapSort(int arr[], int N) { // Construire le tas maximum pour (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, je);  // Tri par tas pour (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]);  // Heapify l'élément racine // pour obtenir à nouveau l'élément le plus élevé // à la racine heapify(arr, i, 0);  } } // Une fonction utilitaire pour imprimer un tableau de taille n void printArray(int arr[], int N) { for (int i = 0; i< N; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver's code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function call  heapSort(arr, N);  printf('Sorted array is
');  printArray(arr, N); } // This code is contributed by _i_plus_plus_.>
Java 
// Java program for implementation of Heap Sort public class HeapSort {  public void sort(int arr[])  {  int N = arr.length;  // Build heap (rearrange array)  for (int i = N / 2 - 1; i>= 0 ; je--) heapify(arr, N, je);  // Extrait un par un un élément du tas pour (int i = N - 1; i> 0; i--) { // Déplace la racine actuelle vers la fin int temp = arr[0];  arr[0] = arr[je];  arr[i] = temp;  // appelle max heapify sur le tas réduit heapify(arr, i, 0);  } } // Pour regrouper un sous-arbre enraciné avec le nœud i qui est // un index dans arr[]. n est la taille du tas void heapify(int arr[], int N, int i) { int plus grand = i; // Initialise le plus grand en tant que racine int l = 2 * i + 1 ; // gauche = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Si l'enfant de gauche est plus grand que la racine if (l< N && arr[l]>arr[le plus grand]) le plus grand = l;  // Si l'enfant de droite est plus grand que le plus grand jusqu'à présent if (r< N && arr[r]>arr[le plus grand]) le plus grand = r;  // Si le plus grand n'est pas racine if (largest != i) { int swap = arr[i];  arr[i] = arr[le plus grand];  arr[le plus grand] = échanger;  // Heapify récursivement le sous-arbre affecté heapify(arr, N, plus grand);  } } /* Une fonction utilitaire pour imprimer un tableau de taille n */ static void printArray(int arr[]) { int N = arr.length;  pour (int je = 0; je< N; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver's code  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = arr.length;  // Function call  HeapSort ob = new HeapSort();  ob.sort(arr);  System.out.println('Sorted array is');  printArray(arr);  } }>
C# 
// C# program for implementation of Heap Sort using System; public class HeapSort {  public void sort(int[] arr)  {  int N = arr.Length;  // Build heap (rearrange array)  for (int i = N / 2 - 1; i>= 0 ; je--) heapify(arr, N, je);  // Extrait un par un un élément du tas pour (int i = N - 1; i> 0; i--) { // Déplace la racine actuelle vers la fin int temp = arr[0];  arr[0] = arr[je];  arr[i] = temp;  // appelle max heapify sur le tas réduit heapify(arr, i, 0);  } } // Pour regrouper un sous-arbre enraciné avec le nœud i qui est // un index dans arr[]. n est la taille du tas void heapify(int[] arr, int N, int i) { int plus grand = i; // Initialise le plus grand en tant que racine int l = 2 * i + 1 ; // gauche = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Si l'enfant de gauche est plus grand que la racine if (l< N && arr[l]>arr[le plus grand]) le plus grand = l;  // Si l'enfant de droite est plus grand que le plus grand jusqu'à présent if (r< N && arr[r]>arr[le plus grand]) le plus grand = r;  // Si le plus grand n'est pas racine if (largest != i) { int swap = arr[i];  arr[i] = arr[le plus grand];  arr[le plus grand] = échanger;  // Heapify récursivement le sous-arbre affecté heapify(arr, N, plus grand);  } } /* Une fonction utilitaire pour imprimer un tableau de taille n */ static void printArray(int[] arr) { int N = arr.Length;  pour (int je = 0; je< N; ++i)  Console.Write(arr[i] + ' ');  Console.Read();  }  // Driver's code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6, 7 };  int N = arr.Length;  // Function call  HeapSort ob = new HeapSort();  ob.sort(arr);  Console.WriteLine('Sorted array is');  printArray(arr);  } } // This code is contributed // by Akanksha Rai(Abby_akku)>
Javascript 
// JavaScript program for implementation // of Heap Sort  function sort( arr)  {  var N = arr.length;  // Build heap (rearrange array)  for (var i = Math.floor(N / 2) - 1; i>= 0 ; je--) heapify(arr, N, je);  // Extrait un par un un élément du tas pour (var i = N - 1; i> 0; i--) { // Déplace la racine actuelle vers la fin var temp = arr[0];  arr[0] = arr[je];  arr[i] = temp;  // appelle max heapify sur le tas réduit heapify(arr, i, 0);  } } // Pour regrouper un sous-arbre enraciné avec le nœud i qui est // un index dans arr[]. n est la taille de la fonction de tas heapify(arr, N, i) { var plus grand = i; // Initialise le plus grand en tant que racine var l = 2 * i + 1; // gauche = 2*i + 1 var r = 2 * i + 2; // right = 2*i + 2 // Si l'enfant de gauche est plus grand que la racine if (l< N && arr[l]>arr[le plus grand]) le plus grand = l;  // Si l'enfant de droite est plus grand que le plus grand jusqu'à présent if (r< N && arr[r]>arr[le plus grand]) le plus grand = r;  // Si le plus grand n'est pas racine if (largest != i) { var swap = arr[i];  arr[i] = arr[le plus grand];  arr[le plus grand] = échanger;  // Heapify récursivement le sous-arbre affecté heapify(arr, N, plus grand);  } } /* Une fonction utilitaire pour imprimer un tableau de taille n */ function printArray(arr) { var N = arr.length;  pour (var je = 0; je< N; ++i)  document.write(arr[i] + ' ');    }  var arr = [12, 11, 13, 5, 6, 7];  var N = arr.length;  sort(arr);  document.write( 'Sorted array is');  printArray(arr, N); // This code is contributed by SoumikMondal>
PHP 
 // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$le plus grand]) $le plus grand = $l; // Si l'enfant de droite est plus grand que le plus grand jusqu'à présent si ($r< $N && $arr[$r]>$arr[$le plus grand]) $le plus grand = $r; // Si le plus grand n'est pas racine if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$le plus grand]; $arr[$le plus grand] = $échange; // Heapify récursivement le sous-arbre affecté heapify($arr, $N, $largest); } } // fonction principale pour effectuer le tri par tas, fonction heapSort(&$arr, $N) { // Construire un tas (réorganiser le tableau) pour ($i = $N / 2 - 1 ; $i>= 0 ; $i- -) heapify($arr, $N, $i); // Extrait un par un un élément du tas pour ($i = $N-1; $i> 0; $i--) { // Déplace la racine actuelle vers la fin $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // appelle max heapify sur le tas réduit heapify($arr, $i, 0); } } /* Une fonction utilitaire pour imprimer un tableau de taille n */ function printArray(&$arr, $N) { for ($i = 0; $i< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>>
Python3 
# Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, N, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra>
Sortir 
Sorted array is 5 6 7 11 12 13>

Analyse de la complexité de Tri en tas

Complexité temporelle : O(N log N)
Espace auxiliaire : O(log n), en raison de la pile d'appels récursifs. Cependant, l'espace auxiliaire peut être O(1) pour une implémentation itérative.

Points importants concernant le tri par tas :

  • Le tri par tas est un algorithme sur place.
  • Son implémentation typique n'est pas stable mais peut être rendue stable (voir ce )
  • Généralement 2 à 3 fois plus lent que bien mis en œuvre Tri rapide . La raison de la lenteur est un manque de localité de référence.

Avantages du tri par tas :

  • Complexité temporelle efficace : Heap Sort a une complexité temporelle de O(n log n) dans tous les cas. Cela le rend efficace pour trier de grands ensembles de données. Le journal m Le facteur provient de la hauteur du tas binaire et garantit que l'algorithme maintient de bonnes performances même avec un grand nombre d'éléments.
  • Utilisation de la mémoire - L'utilisation de la mémoire peut être minime (en écrivant un heapify() itératif au lieu d'un récursif). Ainsi, hormis ce qui est nécessaire pour contenir la liste initiale des éléments à trier, il n'a besoin d'aucun espace mémoire supplémentaire pour fonctionner.
  • Simplicité – Il est plus simple à comprendre que d’autres algorithmes de tri tout aussi efficaces car il n’utilise pas de concepts informatiques avancés tels que la récursivité.

Inconvénients du tri par tas :

  • Cher : Le tri par tas est coûteux car les constantes sont plus élevées que le tri par fusion même si la complexité temporelle est O(n Log n) pour les deux.
  • Instable : Le tri par tas est instable. Cela pourrait réorganiser l’ordre relatif.
  • Efficace: Heap Sort n'est pas très efficace lorsque vous travaillez avec des données très complexes.

Foire aux questions concernant le tri par tas

T1. Quelles sont les deux phases du Heap Sort ?

L'algorithme de tri par tas se compose de deux phases. Dans la première phase, le tableau est converti en un tas maximum. Et dans la deuxième phase, l'élément le plus élevé est supprimé (c'est-à-dire celui à la racine de l'arbre) et les éléments restants sont utilisés pour créer un nouveau tas maximum.

Q2. Pourquoi Heap Sort n’est pas stable ?

L'algorithme de tri par tas n'est pas un algorithme stable car nous échangeons arr[i] avec arr[0] dans heapSort(), ce qui pourrait modifier l'ordre relatif des clés équivalentes.

Q3. Heap Sort est-il un exemple de l’algorithme Divide and Conquer ?

lister sous forme de tableau

Le tri en tas est PAS pas du tout un algorithme Divide and Conquer. Il utilise une structure de données en tas pour trier efficacement son élément et non une approche diviser pour régner pour trier les éléments.

Q4. Quel algorithme de tri est le meilleur : tri par tas ou tri par fusion ?

La réponse réside dans la comparaison de leur complexité temporelle et de leurs besoins en espace. Le tri par fusion est légèrement plus rapide que le tri par tas. Mais d’un autre côté, le tri par fusion prend de la mémoire supplémentaire. En fonction des besoins, il faut choisir lequel utiliser.

Q5. Pourquoi le tri par tas est-il meilleur que le tri par sélection ?

Le tri par tas est similaire au tri par sélection, mais avec une meilleure façon d'obtenir le maximum d'éléments. Il profite de la structure de données du tas pour obtenir le maximum d'éléments en temps constant