Tri par tas en Java

Heapsort en Java est une technique de tri basée sur une comparaison, où la structure de données Binary Heap est utilisée. Ce tri est quasiment le même que celui du tri par sélection, où l'élément le plus grand sera sélectionné, et placé à la fin, et le processus sera répété pour tous les éléments. Afin de comprendre le tri par tas, voyons ce qu'est le tri par tas binaire en Java.

• Structure de données arborescente.
• Arbre binaire complet.
• Il peut avoir jusqu'à deux enfants.
• La valeur dans le nœud racine peut être supérieure (Max Heap) ou plus petite (Min Heap)

Comment fonctionne le tri par tas en Java ?

Avant de passer à l'algorithme, voyons ce qu'est Heapify.

PUBLICITÉ Cours populaire dans cette catégorie MAÎTRISÉE JAVA - Spécialisation | 78 séries de cours | 15 tests simulés

Heapifier

Une fois qu'un tas est créé avec les données d'entrée, la propriété du tas peut ne pas être satisfaite. Pour y parvenir, une fonction appelée heapify sera utilisée pour ajuster les nœuds du tas. Si nous voulons créer un tas maximum, l'élément actuel sera comparé à ses enfants, et si la valeur des enfants est supérieure à l'élément actuel, l'échange se fera avec le plus grand élément d'un enfant gauche ou droit. De même, si un tas min doit être créé, l'échange sera effectué avec le plus petit élément de l'enfant gauche ou droit. Par exemple, ce qui suit est notre tableau d'entrée,

Nous pouvons considérer cela comme un arbre au lieu d'un tableau. Le premier élément sera la racine ; le second sera l'enfant gauche de la racine ; le troisième élément sera le bon enfant de la racine, et ainsi de suite.

Afin de transformer le tas en arbre, parcourez l'arbre dans une direction ascendante. Puisque les nœuds feuilles n’ont pas d’enfants, passons au niveau suivant. c'est-à-dire est 5 et 7.

On peut commencer à 5 heures car c'est à gauche. Ici, 5 a deux enfants : 9 et 4, où 9 est supérieur au nœud parent 5. Pour agrandir les parents, nous échangerons 5 et 9. Après l'échange, l'arbre sera comme indiqué ci-dessous.

Passons à l'élément suivant, 7, où 8 et 2 sont les enfants. Semblable aux éléments 9 et 4, 7 et 8 seront échangés comme dans l'arborescence ci-dessous.

Enfin, 3 a deux enfants-9 et 8, où 9 est le plus grand parmi les enfants et la racine. Ainsi, l’échange de 3 et 9 sera effectué pour agrandir la racine. Répétez le processus jusqu'à ce qu'un tas valide soit formé, comme indiqué ci-dessous.

Algorithme de tri en tas par ordre croissant

1. Créer un tas maximum avec les données d'entrée
2. Remplacez le dernier élément par le plus grand élément du tas
3. Entassez l'arbre
4. Répétez le processus jusqu'à ce que le tableau soit trié

Algorithme de tri par tas par ordre décroissant

1. Créer un Min Heap avec les données d'entrée
2. Remplacez le dernier élément par le plus petit élément du tas
3. Entassez l'arbre
4. Répétez le processus jusqu'à ce que le tableau soit trié

Maintenant, essayons de trier le tas obtenu ci-dessus par ordre croissant en utilisant l'algorithme donné. Tout d’abord, supprimez le plus gros élément. c'est-à-dire root et remplacez-le par le dernier élément.

Maintenant, empilez l'arbre formé et insérez l'élément supprimé dans le dernier du tableau, comme indiqué ci-dessous.

Encore une fois, supprimez l'élément racine, remplacez-le par le dernier élément et Heapify.

Insérez l'élément supprimé à la position vacante. Vous pouvez maintenant voir que la fin du tableau est en cours de tri.

Maintenant, supprimez l'élément 7 et remplacez-le par 2.

Agrandissez l'arbre, comme indiqué ci-dessous.

Répétez le processus jusqu'à ce que le tableau soit trié. Suppression de l'élément 5.

Entasser l'arbre.

Suppression de l'élément 4.

Encore une fois. 

Enfin, un tableau trié comme celui-ci sera formé.

Exemples

Voyons maintenant le code source de Heap Sort en Java

//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort {
public void sort(int array[]) {
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) {
int x = array[0];//largest element(It is available in the root)
array[0] = array[i];
array[i] = x;
// Recursively call <u>heapify</u> until a heap is formed
heapify(array, i, 0);
}
}
// <u>Heapify</u> function
void heapify(int array[], int SizeofHeap, int i) {
int largestelement = i; // Set largest element as root
int leftChild  = 2*i + 1; // index of left child = 2*i + 1
int rightChild  = 2*i + 2; //index of right child  = 2*i + 2
// left child is greater than root
if (leftChild  < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild  < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If <u>largestelement</u> is not root
if (largestelement != i) {
int temp = array[i];
array[i] = array[largestelement];
array[largestelement] = temp;
// Recursive call to  heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
}
}
public static void main(String args[]) {
int array[] = {3,5,7,9,4,8,2};
System.<em>out</em>.println("Input array is: " + Arrays.<em>toString</em>(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.<em>out</em>.println("Sorted array is : " + Arrays.<em>toString</em>(array));
}
}

Sortie

Conclusion

Heap Sort est une technique de tri qui dépend de la structure des données binaires. Il est presque similaire au tri par sélection et n'utilise pas de tableaux séparés pour le tri et le tas.

 Articles recommandés

Ceci a été un guide sur le tri par tas en Java. Ici, nous discutons du fonctionnement de l'algorithme de tri avec ordre croissant et décroissant et des exemples avec un exemple de code. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus –

1. Fusionner le tri en Java
2. Tri par tas en C
3. Tri par tas en C++
4. Tri de sélection dans la structure des données

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!