Un tas (heap) est une structure de données en arbre spécialisée qui respecte la propriété de tas :
🗼
Si P est le nœud parent de C, alors la valeur de P est supérieure ou égale (dans un max-heap) ou inférieure ou égale (dans un min-heap) à la valeur de C.
Un exemple de max-heap avec 8 nœuds
Il existe deux types principaux de tas :
Max Heap : La valeur du nœud parent doit être supérieure ou égale à celle de ses nœuds enfants.
Min Heap : La valeur du nœud parent doit être inférieure ou égale à celle de ses nœuds enfants.
Nous allons nous concentrer sur le max-heap, car la plupart des bibliothèques standard implémentent un max-heap pour les files de priorité. Dans un max-heap, la racine de l’arbre est l’élément le plus grand, tandis que les feuilles sont les plus petites. En revanche, il n’y a pas d’ordre particulier parmi les feuilles. La seule garantie est que le nœud racine est le plus grand élément, et que ses nœuds enfants sont inférieurs ou égaux à sa valeur.
Notez que la dernière rangée du tas est toujours remplie de gauche à droite. Ainsi, la feuille la plus à gauche est placée en premier, et la feuille la plus à droite en dernier – comme le montre l’illustration ci-dessus.
Implémentation
Un tas peut être implémenté sous forme de tableau, où le premier élément représente la racine. Comme chaque nœud n’a que deux enfants, on peut organiser les indices de la manière suivante :
La racine possède un indice égal à 1.
Les enfants gauche et droit se trouvent respectivement aux indices 2i et 2i+1 pour tous les nœuds.
Le nœud parent d’un élément situé à l’indice i se trouve à l’indice i // 2.
Le tas ci-dessus peut être représenté dans une liste comme suit :
# Just read every line in the picture and write the numbers side by side
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# Or to see it better visually
heap = [None, # We skip the index [0] to have a simpler indexing
8, # Index [1]
5, 7, # Indices [2, 3]
1, 1, 6, 3, # Indices [4, 5, 6, 7]
1] # Index [8]
Défi : Vérifier si l’arbre binaire est un tas
Étant donné un arbre binaire représenté par un tableau de n nombres (avec l’indexation décrite ci-dessus), on vous demande de vérifier s’il respecte les propriétés du max-heap.
Entrée
La première ligne de l’entrée contient un entier n (1 ≤ n ≤ 100 000).
La ligne suivante contient n entiers séparés par des espaces, () qui représentent les valeurs des éléments du tas.
Sortie
Le programme doit afficher Yes si l’arbre binaire en entrée respecte la propriété de max-heap, et No dans le cas contraire.
Exemples
Input
Output
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Explication
Exemple 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Exemple 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
