Tutoriel de structure de données de tas

Les données sont un ensemble de valeurs. Les données peuvent être collectées et mises en ligne, ou dans une colonne, ou dans un tableau ou sous la forme d'un arbre. La structure des données n'est pas seulement le placement des données dans l'une de ces formes. En informatique, la structure de données est l'un de ces formats, plus la relation entre les valeurs, plus les opérations (fonctions) fonctionnent sur les valeurs. Vous devriez déjà avoir des connaissances de base sur la structure des données des arbres avant de venir ici, car les concepts là-bas seront utilisés ici avec peu ou pas d'explication. Si vous n'avez pas ces connaissances, alors lisez le tutoriel intitulé, Tree Data Structure Tutoriel pour les débutants, sur le lien, https: // Linuxhint.com / arbre_data_structure_tutorial_beginners /. Après cela, continuez à lire ce tutoriel.Une structure de données de tas est un arbre binaire complet ou presque complet, où l'enfant de chaque nœud est égal à une valeur en valeur ou moins que la valeur de son parent. Alternativement, c'est un tel arbre où la valeur d'un parent est égale ou inférieure à la valeur de l'un de ses enfants. La valeur (donnée) d'une arbre est également appelée la clé.

Illustration des structures de données de tas

Il existe deux types de tas: un maximum et un min-heap. Une structure maximale est l'endroit où la valeur maximale est la racine, et les valeurs deviennent plus petites à mesure que l'arbre est descendu; Tout parent est égal à une valeur ou plus grande que l'un ou l'autre de ses enfants immédiats. Une structure min-t-hap est l'endroit où la valeur minimale est la racine, et les valeurs deviennent plus grandes lorsque l'arbre est descendu; Tout parent est égal à une valeur ou plus petite que l'un de ses enfants immédiats. Dans les diagrammes suivants, le premier est un maximum et le second est un mine-heap:

Pour les deux tas, notez que pour une paire d'enfants, peu importe que celle de gauche soit la plus grande valeur. Une rangée dans un niveau dans l'arbre, ne doit pas nécessairement être remplie du minimum au maximum, de la gauche; il n'est pas nécessairement rempli du maximum au minimum, à partir de la gauche.

Représentant un tas dans un tableau

Pour que les logiciels utilisent facilement un tas, le tas doit être représenté dans un tableau. Le maximum-HEAP ci-dessus, représenté dans un tableau est:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69

Cela se fait en commençant par la valeur racinaire comme la première valeur pour le tableau. Les valeurs sont placées en continu en lisant l'arbre de gauche à droite, de haut en bas. Si un élément est absent, sa position dans le tableau est ignorée. Chaque nœud a deux enfants. Si un nœud est à l'index (position) n, son premier enfant dans le tableau est à l'index 2n + 1, et son prochain enfant est à l'index 2n + 2. 89 est à l'index 0; son premier enfant, 85 est à l'index 2 (0) + 1 = 1 tandis que son deuxième enfant est à l'index 2 (0) + 2 = 2. 85 est à l'indice 1; Son premier enfant, 84, est à l'index 2 (1) + 1 = 3 Alors que son deuxième enfant, 82 est à l'index 2 (1) + 2 = 4. 79 est à l'index 5; son premier enfant, 65 est à l'index 2 (5) + 1 = 11 tandis que son deuxième enfant est à l'index 2 (5) + 2 = 12. Les formules sont appliquées au reste des éléments du tableau.

Un tel tableau, où la signification d'un élément et la relation entre les éléments, est impliquée par la position de l'élément, est appelée structure de données implicite.

La structure de données implicite pour le mine-heap ci-dessus est:

65, 68, 70, 73, 71, 83, 84 ,,, 79, 80 ,,, 85, 89

Le max-hap ci-dessus est un arbre binaire complet mais pas un arbre binaire complet. C'est pourquoi certains emplacements (positions) sont vides dans le tableau. Pour un arbre binaire complet, aucun emplacement ne sera vide dans le tableau.

Maintenant, si le tas était un arbre presque complet, par exemple, si la valeur 82 manquait, le tableau serait:

89, 85, 87, 84 ,, 79, 73, 80, 81 ,,, 65, 69

Dans cette situation, trois emplacements sont vides. Cependant, les formules sont toujours applicables.

Opérations

Une structure de données est un format de données (e.g. un arbre), plus la relation entre les valeurs, plus les opérations (fonctions) effectuent sur les valeurs. Pour un tas, la relation qui traverse l'ensemble du tas est que le parent doit être égal ou supérieur à la valeur que les enfants, pour un maximum; et le parent doit être égal ou inférieur à la valeur que les enfants, pour un mine-heap. Cette relation est appelée la propriété du tas. Les opérations d'un tas sont regroupées sous les rubriques de la création, de base, interne et d'inspection. Un résumé des opérations du tas suit:

Résumé des opérations de tas

Certaines opérations logicielles sont courantes avec des tas, comme suit:

Création d'un tas

create_heap: créer un tas signifie former un objet qui représente le tas. Dans la langue C, vous pouvez créer un tas avec le type d'objet struct. L'un des membres de la structure sera le tableau de tas. Le reste des membres sera des fonctions (opérations) pour le tas. Create_heap signifie créer un tas vide.

Tas: le tableau de tas est un tableau partiellement trié (ordonné). HEAPify signifie, fournissez un tableau de tas à partir d'un tableau non trié - voir les détails ci-dessous.

Merge: Cela signifie, former un tas d'union à partir de deux tas différents - voir les détails ci-dessous. Les deux tas doivent être à la fois max ou les deux min-heap. Le nouveau tas est conforme à la propriété du tas, tandis que les tas d'origine sont conservés (non effacés).

Meld: Cela signifie, rejoignez deux tas du même type pour en former un nouveau, en maintenant les doublons - voir les détails ci-dessous. Le nouveau tas est conforme à la propriété du tas, tandis que les tas d'origine sont détruits (effacés). La principale différence entre la fusion et la fusion est que pour la fusion, un arbre s'adapte en tant que sous-arbre à la racine de l'autre arbre, permettant des valeurs en double dans le nouvel arbre, tandis que pour la fusion, un nouvel arbre de tas se forme, en supprimant des doublons. Il n'est pas nécessaire de maintenir les deux tas d'origine avec la fusion.

Opérations de tas de base

find_max (find_min): localisez la valeur maximale dans le tableau maximum et renvoyez une copie, ou localisez la valeur minimale dans le tableau Min-Heap et renvoyez une copie.

Insérer: ajoutez un nouvel élément au tableau de tas et réorganisez le tableau afin que la propriété tas du diagramme soit maintenue.

Extract_Max (extract_min): Localisez la valeur maximale dans le tableau maximum-HEAP, supprimez-le et renvoyez; ou localisez la valeur minimale dans le tableau Min-Heap, supprimez-le et renvoyez-le.

Delete_max (Delete_Min): Localisez le nœud racine d'un max-heap, qui est le premier élément du tableau max-heap, retirez-le sans nécessairement le retourner; ou localisez le nœud racine d'un mine-heap, qui est le premier élément du tableau Min-Heap, le retirez sans nécessairement le retourner;

Remplacer: localisez le nœud racine de l'un ou l'autre tas, retirez-le et remplacez-le par un nouveau. Peu importe que l'ancienne racine soit retournée.

Opérations de tas internes

Augmentation_Key (DEMPRED_KEY): Augmentez la valeur de tout nœud pour un maximum de max et réorganisez afin que la propriété du tas soit maintenue, ou diminuez la valeur de tout nœud pour un mine-heap et réorganise afin que la propriété du tas soit maintenue.

Supprimer: Supprimer n'importe quel nœud, puis réorganiser, afin que la propriété du tas soit maintenue pour le max-hap ou un min-heap.

Shift_up: déplacez un nœud dans un maximum-hap ou min-heap tant que nécessaire, en réarrangeant pour maintenir la propriété du tas.

Shift_down: déplacez un nœud dans un maximum-hap ou min-heap tant que nécessaire, en réarrangeant pour maintenir la propriété du tas.

Inspection d'un tas

Taille: Cela renvoie le nombre de clés (valeurs) dans un tas; il n'inclut pas les emplacements vides du réseau de tas. Un tas peut être représenté par le code, comme dans le diagramme ou avec un tableau.

est vide: Cela renvoie Boolean True s'il n'y a pas de nœud dans un tas, ou booléen faux si le tas a au moins un nœud.

Tamiser un tas

Il y a du tamisage et des tamis:

Tamiser: Cela signifie échanger un nœud avec son parent. Si la propriété du tas n'est pas satisfaite, échangez le parent avec son propre parent. Continuez de cette façon sur le chemin jusqu'à ce que la propriété du tas soit satisfaite. La procédure peut atteindre la racine.

Tamis-down: Cela signifie échanger un nœud de grande valeur avec le plus petit de ses deux enfants (ou un enfant pour un tas presque complet). Si la propriété du tas n'est pas satisfaite, échangez le nœud inférieur avec le nœud plus petit de ses deux enfants. Continuez de cette façon sur le chemin jusqu'à ce que la propriété du tas soit satisfaite. La procédure peut atteindre une feuille.

Tas

HEAPIFY signifie trier un tableau non trié pour que la propriété du tas soit satisfaite pour Max-Heap ou Min-Heap. Cela signifie qu'il pourrait y avoir des emplacements vides dans le nouveau tableau. L'algorithme de base pour tasser un max-heap ou mine-heap est le suivant:

- Si le nœud racine est plus extrême que l'un ou l'autre du nœud de son enfant, échangez la racine avec le nœud enfant moins extrême.

- Répétez cette étape avec les nœuds d'enfants dans un schéma de traversée d'arbre en précommande.

L'arbre final est un arbre de tas satisfaisant la propriété du tas. Un tas peut être représenté comme un diagramme d'arbres ou dans un tableau. Le tas résultant est un arbre partiellement trié, je.e. un tableau partiellement trié.

Détails de l'opération de tas

Cette section de l'article donne les détails des opérations de tas.

Création d'un tas de détails

create_heap

Voir au dessus!

s'accélérer

Voir au dessus

fusionner

Si le tas se réalise,

89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69

et

89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71

sont fusionnés, le résultat sans doublons peut être,

89, 85, 87, 84, 82, 83, 81, 80, 79 ,, 73, 68, 65, 69, 70, 71

Après un peu de tamis. Notez que dans le premier tableau, 82 n'a pas d'enfants. Dans le tableau résultant, il se trouve à l'index 4; et ses emplacements à l'index 2 (4) + 1 = 9 et 2 (4) + 2 = 10 sont vacants. Cela signifie qu'il n'a pas non plus d'enfants dans le nouveau diagramme d'arbres. Les deux tas d'origine ne doivent pas être supprimés car leurs informations ne sont pas vraiment dans le nouveau tas (nouveau tableau). L'algorithme de base pour fusionner des tas du même type est comme suit:

- Rejoignez un tableau au bas de l'autre tableau.

- Heapify élimine les doublons, s'assurant que les nœuds qui n'avaient pas d'enfants dans les tas d'origine, n'ont toujours pas d'enfants dans le nouveau tas.

fondre

L'algorithme pour fusionner deux tas du même type (deux max ou deux minutes) est le suivant:

- Comparez les deux nœuds racine.

- Faire la racine moins extrême et le reste de son arbre (sous-arbre), le deuxième enfant de la racine extrême.

- Tamiser l'enfant errant de la racine de maintenant le sous-arbre extrême, vers le bas dans le sous-arbre extrême.

Le tas résultant est toujours conforme à la propriété du tas, tandis que les tas d'origine sont détruits (effacés). Les tas d'origine peuvent être détruits car toutes les informations qu'ils possédaient se trouvent toujours dans le nouveau tas.

Opérations de tas de base

find_max (find_min)

Cela signifie localiser la valeur maximale dans le tableau maximum et renvoyer une copie, ou localiser la valeur minimale dans le tableau Min-Heap et renvoyer une copie. Un tableau de tas, par définition, satisfait déjà la propriété du tas. Alors, retournez simplement une copie du premier élément du tableau.

insérer

Cela signifie ajouter un nouvel élément au tableau de tas et réorganiser le tableau afin que la propriété du tas du diagramme soit maintenue (satisfait). L'algorithme pour le faire pour les deux types de tas est le suivant:

- Supposons un arbre binaire complet. Cela signifie que le tableau doit être rempli à la fin avec des emplacements vides si nécessaire. Le nombre total de nœuds d'un tas complet est de 1, ou 3 ou 7 ou 15 ou 31, etc.; Continuez à doubler et à ajouter 1.

- Mettez le nœud dans l'emplacement vide le plus approprié par magnitude, vers l'extrémité du tas (vers la fin du réseau de tas). S'il n'y a pas d'emplacement vide, alors démarrez une nouvelle ligne en bas à gauche.

- Tamiser si nécessaire, jusqu'à ce que la propriété du tas soit satisfaite.

extract_max (extract_min)

Localisez la valeur maximale dans le tableau maximum, supprimez-le et renvoyez-le; ou localisez la valeur minimale dans le tableau Min-Heap, supprimez-le et renvoyez-le. L'algorithme à extraire_max (extract_min) est le suivant:

- Retirez le nœud racine.

- Prenez (supprimez) le nœud le plus à droite inférieur (dernier nœud dans le tableau) et placez-vous à la racine.

- Tamiser le cas échéant, jusqu'à ce que la propriété du tas soit satisfaite.

Delete_max (Delete_min)

Localisez le nœud racine d'un max-heap, qui est le premier élément du tableau de tas max, retirez-le sans nécessairement le retourner; ou localisez le nœud racine d'un mine-heap, qui est le premier élément du tableau Min-Hap, retirez-le sans nécessairement le retourner. L'algorithme pour supprimer le nœud racine est le suivant:

- Retirez le nœud racine.

- Prenez (supprimez) le nœud le plus à droite inférieur (dernier nœud dans le tableau) et placez-vous à la racine.

- Tamiser le cas échéant, jusqu'à ce que la propriété du tas soit satisfaite.

remplacer

Localisez le nœud racine de l'un ou l'autre tas, retirez-le et remplacez-le par le nouveau. Peu importe que l'ancienne racine soit retournée. Tamiser le cas échéant, jusqu'à ce que la propriété du tas soit satisfaite.

Opérations de tas internes

Augmente_Key (DIMPRED_KEY)

Augmentez la valeur de n'importe quel nœud pour un maximum de tas et réorganisez afin que la propriété du tas soit maintenue, ou diminuez la valeur de n'importe quel nœud pour un mine-heap et réorganise afin que la propriété du tas soit maintenue. Tamiser le haut ou vers le bas si approprié, jusqu'à ce que la propriété du tas soit satisfaite.

supprimer

Retirez le nœud d'intérêt, puis réorganisez, afin que la propriété du tas soit maintenue pour le maximum ou un min-heap. L'algorithme pour supprimer un nœud est le suivant:

- Supprimer le nœud d'intérêt.

- Prendre (supprimer) le nœud le plus à droite inférieur (dernier nœud dans le tableau) et placer à l'index du nœud supprimé. Si le nœud supprimé est à la dernière ligne, alors cela peut ne pas être nécessaire.

- Tamiser le haut ou vers le bas si approprié, jusqu'à ce que la propriété du tas soit satisfaite.

décale vers le haut

Déplacez un nœud vers le haut dans un maximum de tas max ou de mine aussi longtemps que nécessaire, en réorganisant pour maintenir la propriété du tas - tamisez.

rétrograder

Déplacez un nœud vers le bas dans un maximum de tas ou de mine aussi longtemps que nécessaire, en réorganisant pour maintenir la propriété du tas - tamisez vers le bas.

Inspection d'un tas

taille

Voir au dessus!

est vide

Voir au dessus!

Autres classes de tas

Le tas décrit dans cet article peut être considéré comme le tas principal (général). Il y a d'autres classes de tas. Cependant, les deux que vous devriez savoir au-delà de cela sont le tas binaire et le tas D-AY.

Tas binaire

Le tas binaire est similaire à ce tas principal, mais avec plus de contraintes. En particulier, le tas binaire doit être un arbre complet. Ne confondez pas entre un arbre complet et un arbre plein.

tas d-ary

Un tas binaire est un tas à 2 armes. Un tas où chaque nœud a 3 enfants est un tas à 3 armes. Un tas où chaque nœud a 4 enfants est un tas 4-armé, et ainsi de suite. Un tas d-ary a d'autres contraintes.

Conclusion

Un tas est un arbre binaire complet ou presque complet, qui satisfait la propriété du tas. La propriété du tas a 2 alternatives: pour un maximum, un parent doit être égal ou supérieur à la valeur que les enfants immédiats; Pour un min-heap, un parent doit être égal ou inférieur à la valeur que les enfants immédiats. Un tas peut être représenté comme un arbre ou dans un tableau. Lorsqu'il est représenté dans un tableau, le nœud racine est le premier nœud du tableau; Et si un nœud est à l'index n, son premier enfant dans le tableau est à l'index 2n + 1 et son prochain enfant est à l'index 2n + 2. Un tas a certaines opérations qui sont effectuées sur le tableau.

Chrys