Introduction au tri en tas en Java

Heapsort en Java est une technique de tri basée sur la comparaison, où la structure de données Binary Heap est utilisée. Ce tri est presque le même que celui du tri par sélection où le plus grand élément sera sélectionné et placé à la fin et le processus sera répété pour tous les éléments. Afin de comprendre Heap Sort, voyons ce que Binary Heap Sort 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 Heap Sort en Java?

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

Heapify

Une fois un segment de mémoire créé avec les données d'entrée, la propriété du segment de mémoire 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 max, l'élément actuel sera comparé à ses enfants et si la valeur des enfants est supérieure à l'élément actuel, l'échange sera effectué avec le plus grand élément d'un enfant gauche ou droit. De même, si min-heap 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 root, le second sera l'enfant gauche de root, le troisième élément sera l'enfant droit de root et ainsi de suite.

Afin de transformer le tas en arbre, traversez l'arbre dans une direction ascendante. Étant donné que les nœuds feuilles n'ont pas d'enfants, examinons le niveau suivant. soit 5 et 7.

On peut commencer à 5 comme 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 allons échanger 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 plus élevé 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 segment valide soit formé, comme illustré ci-dessous.

Algorithme de tri des segments de mémoire par ordre croissant

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

Algorithme de tri des segments de mémoire par ordre décroissant

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

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

Maintenant, tassez 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 tassez-le.

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

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

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

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

Heapification de l'arbre.

Retrait de l'élément 4.

Heapfying à nouveau.

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

Exemples pour implémenter le tri en tas en Java

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 heapify until a heap is formed
heapify(array, i, 0);
)
)
// Heapify 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 array(largestelement))
largestelement = leftChild ;
//right child is greater than largest
if (rightChild array(largestelement))
largestelement = rightChild ;
// If largestelement 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. out .println("Input array is: " + Arrays. toString (array));
HeapSort obj = new HeapSort();
obj.sort(array);
System. out .println("Sorted array is : " + Arrays. toString (array));
)
)

Production

Conclusion

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

Article recommandé

Cela a été un guide pour le tri de tas en Java. Nous discutons ici 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. Fonctions mathématiques JavaScript
  2. Disposition en Java
  3. Compilateurs Java
  4. Guide de fusion de tri en Java
  5. Guide de tri des segments de mémoire en C
  6. Exemples de tri en tas en C ++

Catégorie:

Développement de logiciels