Représentation matricielle du tas binaire

Un arbre binaire complet qui obéit à la propriété de tri du tas est appelé un tas binaire.

En fonction de la façon dont un tas binaire est trié, il peut être divisé en deux types :

Tas minimal est un tas dans lequel la valeur d'un nœud est supérieure ou égale à la valeur de son nœud parent. Le nœud racine d’un min-heap est le plus petit.

Max tas est un tas où la valeur d'un nœud est inférieure ou égale à la valeur de son nœud parent. Le nœud racine du tas max est le plus grand.

La valeur d'un tas binaire est généralement représentée sous la forme d'un tableau. La représentation matricielle d'un tas binaire est la suivante :

• L'index de l'élément racine est 0.

• Si i est l'index d'un nœud dans le tableau, alors les index des autres nœuds liés à ce nœud sont les suivants :

  • Enfant gauche : (2*i)+1

  • Enfant droit : (2*i )+2

  • Nœud parent : (i-1)/2

En utilisant les règles de représentation de tableau ci-dessus, nous pouvons représenter le tas comme un tableau :

1

4

7

8

9

11

12

Maintenant, nous pouvons discuter des types de tas basés sur le tri

•  : Tas minimum - La racine Le nœud a la valeur minimale. La valeur du nœud est supérieure à la valeur du nœud parent.

Exemple :

Représentation de tableau :

1

4

7

6

9

10

8

• Max Heap - Le nœud racine a la valeur maximale. La valeur du nœud est inférieure à la valeur du nœud parent.

Exemple :

Représentation du tableau :

11

8

9

6

4

5

1

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!