Pile contre tas
Stack est une liste ordonnée dans laquelle l'insertion et la suppression d'éléments de la liste ne peuvent être effectuées qu'à une extrémité appelée le sommet. Pour cette raison, la pile est considérée comme une structure de données LIFO (dernier entré, premier sorti). Le tas est une structure de données spéciale basée sur des arbres et qui satisfait une propriété spéciale appelée propriété du tas. De plus, un tas est un arbre complet, ce qui signifie qu'il n'y a pas d'espace entre les feuilles de l'arbre, c'est-à-dire que dans un arbre complet, chaque niveau est rempli avant d'ajouter un nouveau niveau à l'arbre et les nœuds d'un niveau donné sont remplis à partir de de gauche à droite.
Qu'est-ce que la pile ?
Comme mentionné précédemment, la pile est une structure de données dans laquelle des éléments sont ajoutés et supprimés à partir d'une seule extrémité appelée le sommet. Les piles ne permettent que deux opérations fondamentales appelées push et pop. L'opération push ajoute un nouvel élément au sommet de la pile. L'opération pop supprime un élément du haut de la pile. Si la pile est déjà pleine, lorsqu'une opération push est effectuée, elle est considérée comme un débordement de pile. Si une opération pop est effectuée sur une pile déjà vide, elle est considérée comme un débordement de pile. En raison du petit nombre d'opérations pouvant être effectuées sur une pile, celle-ci est considérée comme une structure de données restreinte. De plus, selon la façon dont les opérations push et pop sont définies, il est clair que les éléments qui ont été ajoutés en dernier dans la pile sortent de la pile en premier. Par conséquent, la pile est considérée comme une structure de données LIFO.
Qu'est-ce que Heap ?
Comme mentionné précédemment, le tas est un arbre complet qui satisfait la propriété du tas. La propriété Heap indique que, si y est un nœud enfant de x, la valeur stockée dans le nœud x doit être supérieure ou égale à la valeur stockée dans le nœud y (c'est-à-dire valeur(x) ≥ valeur(y)). Cette propriété implique que le nœud avec la plus grande valeur serait toujours placé à la racine. Un tas construit à l'aide de cette propriété est appelé un tas max. Il existe une autre variante de la propriété de tas qui indique l'inverse de cela. (c'est-à-dire valeur(x) ≤ valeur(y)). Cela implique que le nœud avec la plus petite valeur serait toujours placé à la racine, ainsi appelé un min-heap. Il existe un large éventail d'opérations effectuées sur les tas, telles que la recherche du minimum (en tas min) ou du maximum (en tas max), la suppression du minimum (en tas min) ou du maximum (en tas max), l'augmentation (en tas max -tas) ou clé décroissante (en min-tas), etc.
Quelle est la différence entre Stack et Heap ?
La principale différence entre les piles et les tas est que si la pile est une structure de données linéaire, le tas est une structure de données non linéaire. Stack est une liste ordonnée qui suit la propriété LIFO, tandis que le tas est un arbre complet qui suit la propriété heap. De plus, la pile est une structure de données restreinte qui ne prend en charge qu'un nombre limité d'opérations telles que push et pop, tandis que le tas prend en charge un large éventail d'opérations telles que la recherche et la suppression du minimum ou du maximum, l'augmentation ou la diminution de la clé et la fusion.
