DAA - Tas binaire

Il existe plusieurs types de tas, cependant dans ce chapitre, nous allons discuter du tas binaire. UNEbinary heapest une structure de données, qui ressemble à un arbre binaire complet. La structure de données du tas obéit aux propriétés de classement décrites ci-dessous. En général, un tas est représenté par un tableau. Dans ce chapitre, nous représentons un tas parH.

Comme les éléments d'un tas sont stockés dans un tableau, en considérant l'index de départ comme 1, la position du nœud parent de ith élément peut être trouvé à ⌊ i/2 ⌋. Enfant gauche et enfant droit deith le nœud est en position 2i et 2i + 1.

Un tas binaire peut être classé comme un max-heap ou un min-heap en fonction de la propriété de commande.

Max-Heap

Dans ce tas, la valeur de clé d'un nœud est supérieure ou égale à la valeur de clé de l'enfant le plus élevé.

Par conséquent, H[Parent(i)] ≥ H[i]

Min-Heap

Dans le tas moyen, la valeur de clé d'un nœud est inférieure ou égale à la valeur de clé de l'enfant le plus bas.

Par conséquent, H[Parent(i)] ≤ H[i]

Dans ce contexte, les opérations de base sont présentées ci-dessous par rapport à Max-Heap. L'insertion et la suppression d'éléments dans et à partir des tas nécessitent un réarrangement des éléments. Par conséquent,Heapify la fonction doit être appelée.

Représentation du tableau

Un arbre binaire complet peut être représenté par un tableau, stockant ses éléments en utilisant la traversée par ordre de niveau.

Considérons un tas (comme indiqué ci-dessous) qui sera représenté par un tableau H.

Considérant l'index de départ comme 0, en utilisant la traversée par ordre de niveau, les éléments sont conservés dans un tableau comme suit.

Index 0 1 2 3 4 5 6 sept 8 ...
elements 70 30 50 12 20 35 25 4 8 ...

Dans ce contexte, les opérations sur le tas sont représentées par rapport à Max-Heap.

Pour trouver l'index du parent d'un élément à l'index i, l'algorithme suivant Parent (numbers[], i) est utilisé.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

L'index de l'enfant gauche d'un élément à l'index i peut être trouvée en utilisant l'algorithme suivant, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

L'index de l'enfant droit d'un élément à l'index i peut être trouvée en utilisant l'algorithme suivant, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL