Comprendre comment implémenter un tas binaire en Java

Cet article vous donnera un aperçu complet du fonctionnement du tri de tas et plus tard, nous apprendrons à implémenter un tas binaire en Java.

Voici l'agenda de cet article:

1. Qu'est-ce que le tri en tas?
2. Tas maximum
3. Tas min
4. Implémentation de tas en Java
   • Diagramme
   • Code

Commençons!

Qu'est-ce que le tri en tas?

Heap est essentiellement une structure de données arborescente. Il a des nœuds. Le nœud comprend certains éléments. Chaque nœud contient un élément.

Les nœuds peuvent avoir des enfants. Si au cas où il n'y aurait pas d'enfants, cela s'appelle une feuille.

Il y a deux règles à suivre:

• La valeur de chaque nœud doit être inférieure ou égale à toutes les valeurs stockées dans ses enfants.
• Il a la plus petite hauteur possible.

Les tas sont extrêmement efficaces pour extraire lesélément le plus petit ou le plus grand.

Passons maintenant au tas min!

comment éviter les blocages en java

Tas min

Le tas min est un arbre binaire complet dans lequel la valeur de l'élément racine est inférieure ou égale à l'un des éléments enfants.

Représentation du tas min

Arr [(i-1) / 2]: cela renverra le nœud parent.

Arr [(2 * i) + 1]: cela retournera le nœud enfant gauche.

Arr [(2 * i) + 2]: cela retournera le bon nœud enfant.

Il existe certaines méthodes de Min Heap:

• insérer(): Une nouvelle clé à la fin de l'arborescence est ajoutée. Dans le cas où la nouvelle clé est plus grande que le parent, alors il n'y a rien à faire, sinon, nous devons traverser pour configurer la propriété de tas.
• getMin (): cette méthode permet de renvoyer l'élément racine.
• extractMin (): cette méthode renvoie le minimumélément.

Passons maintenant au tas Max.

Tas max

Le tas maximum est une arborescence binaire complète dans laquelle la valeur de l'élément racine est supérieure ou égale à l'un des éléments enfants.

Le tas max se compose également de plusieurs méthodes!

• Insérer (): il insérera un élément dans le tas.
• Effacer() : cela supprimera un élément du tas.
• FindMax (): il trouvera l'élément maximum du tas.
• printHeap (): Il imprimera le contenu du tas

Maintenant, laissez-moi vous montrer l'implémentation du tas à travers un diagramme et plus tard un Javacode.

Implémentation de tas en Java

Diagramme:

liste des événements javascript avec exemples

Le diagramme ci-dessus montre le tas binaire en Java. Comme vous avez appris qu'il y a deux tas: tas min et tas max, voici un diagramme:

Maintenant, en passant à notre prochain segment, nous allons voir comment implémenter un tas binaire en Java.

Code:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Ceci initialisera notre tas avec la taille par défaut. * / public BinaryHeap (int capacity) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Cela vérifiera si le tas est vide ou non * Complexité: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Ceci vérifiera si le tas est plein ou non * Complexité: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Ceci insérera un nouvel élément dans le tas * Complexité: O (log N) * Dans le pire des cas, nous devons traverser jusqu'à la racine * / public void insert (int x) {if (isFull ()) throw new NoSuchElementException ('Heap is full, No space to insert nouvel élément ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Cela supprimera l'élément à l'index x * Complexité: O (log N) * * / public int delete (int x) {if (isEmpty ()) throw new NoSuchElementException ('Heap is empty, No element to delete') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Cette méthode permet de conserver la propriété du tas lors de l'insertion d'un élément. * * / private void heapifyUp (int i) {int temp = tas [i] while (i> 0 && temp> tas [parent (i)]) {tas [i] = tas [parent (i)] i = parent (i)} heap [i] = temp} / ** * Cette méthode utilisée pour maintenir la propriété de tas lors de la suppression d'un élément. * * / private void heapifyDown (int i) {int enfant int temp = tas [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Cette méthode utilisée pour imprimer tous les éléments du tas * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 i
Avec cela, nous arrivons à la fin de cet article sur Binary Heap en Java. Vérifiez    par Edureka, une entreprise d'apprentissage en ligne de confiance avec un réseau de plus de 250 000 apprenants satisfaits répartis dans le monde entier. Le cours de formation et de certification Java J2EE et SOA d'Edureka est conçu pour les étudiants et les professionnels qui souhaitent devenir développeur Java. Le cours est conçu pour vous donner une longueur d'avance dans la programmation Java et vous former aux concepts Java de base et avancés ainsi qu'à divers frameworks Java tels que Hibernate et Spring. 
 Vous avez une question pour nous? Veuillez le mentionner dans la section commentaires de ce blog «Java ArrayList» et nous vous répondrons dans les plus brefs délais.