Bonjour,
Dans la leçon précédente, nous avons analysé en détail la complexité du tri rapide, révélant sa performance exceptionnelle en cas moyen () mais aussi sa vulnérabilité à un pire cas quadratique (). Cette dualité motive la recherche d'algorithmes de tri qui, tout en étant efficaces, garantissent une performance en dans tous les cas.
C'est ce qui nous amène à notre sujet du jour. Pour construire un tel algorithme, le tri par tas (heapsort), nous devons d'abord maîtriser la structure de données qui le sous-tend : le tas binaire (en anglais, binary heap).
L'objectif de cette leçon est donc de décrire la propriété d'un tas binaire et son implémentation à l'aide d'un tableau. Comprendre cette structure est une étape fondamentale, non seulement pour le tri, mais aussi pour de nombreuses autres applications comme les files de priorité.
1. Qu'est-ce qu'un tas binaire ? Les deux propriétés fondamentales
Un tas binaire est un type d'arbre binaire qui respecte deux propriétés strictes : une propriété de structure et une propriété d'ordre.
a. La propriété d'ordre : tas-max et tas-min
La propriété d'ordre définit la relation entre la valeur d'un nœud et celle de ses enfants. Il en existe deux variantes :
- Tas-max (Max-Heap) : Pour chaque nœud de l'arbre (sauf la racine), la valeur de ce nœud est inférieure ou égale à la valeur de son père. Conséquence : la racine de l'arbre contient toujours l'élément le plus grand.
- Tas-min (Min-Heap) : Pour chaque nœud (sauf la racine), la valeur de ce nœud est supérieure ou égale à la valeur de son père. Conséquence : la racine contient toujours l'élément le plus petit.
Cette propriété est au cœur de l'efficacité du tas pour retrouver rapidement l'élément extrémal.
b. La propriété de structure : l'arbre binaire complet
La deuxième propriété est plus subtile : un tas doit être un arbre binaire quasi-complet à gauche (en anglais, complete binary tree). Cela signifie que :
- Tous les niveaux de l'arbre sont entièrement remplis, à l'exception possible du dernier.
- Si le dernier niveau n'est pas plein, il doit être rempli de gauche à droite, sans aucun "trou".
Cette contrainte de structure est essentielle, car elle garantit deux choses :
- La hauteur de l'arbre est toujours minimale pour un nombre de nœuds donné, soit .
- Elle permet une implémentation extrêmement compacte et efficace à l'aide d'un simple tableau.
La vidéo suivante explique d'abord comment représenter un arbre dans un tableau, puis définit précisément ce qu'est un arbre binaire complet.
2.6.3 Heap - Heap Sort - Heapify - Priority Queues
Pour comprendre la structure d'un tas, il faut d'abord maîtriser la notion d'arbre binaire complet. Cette vidéo de Abdul Bari explique très clairement ce que cela signifie et pourquoi cette structure est si efficace.
Regardez les deux segments suivants : De 7:22 à 11:13 : Cette partie définit ce qu'est un arbre binaire complet ('complete binary tree'). Portez une attention particulière à l'idée que les niveaux sont remplis de gauche à droite sans 'trous'. De 2:26 à 7:22 : Cette partie montre comment la structure complète d'un arbre permet de le représenter dans un tableau sans perdre d'information et sans utiliser de pointeurs.
2. L'implémentation par tableau
Comme vous venez de le voir, la propriété d'arbre complet rend le tas particulièrement apte à être stocké dans un tableau. On stocke simplement les nœuds niveau par niveau, de gauche à droite.
Cette organisation nous permet de naviguer dans l'arbre (trouver le parent ou les enfants d'un nœud) par de simples calculs arithmétiques sur les indices du tableau, sans avoir besoin de pointeurs explicites.
En adoptant la convention la plus courante en programmation (tableaux indexés à partir de 0), pour un nœud à l'indice i :
- Son parent se trouve à l'indice .
- Son fils gauche se trouve à l'indice .
- Son fils droit se trouve à l'indice .
Note importante pour l'Agrégation :
Sachez qu'il existe une autre convention, parfois utilisée dans les ouvrages théoriques, où les indices commencent à 1. Dans ce cas, les formules deviennent : parent(i) = floor(i/2), fils_gauche(i) = 2i, fils_droit(i) = 2i+1. Il est crucial de connaître les deux et de toujours préciser la convention que vous utilisez. Pour nos implémentations en Python, nous utiliserons systématiquement l'indexation à partir de 0.
3. Définition complète et synthèse
Nous pouvons maintenant énoncer une définition complète et formelle, telle que vous pourriez la présenter.
Définition : Un tas binaire est un arbre binaire quasi-complet à gauche qui satisfait la propriété de tas (soit tas-max, soit tas-min). Dans le contexte de l'Agrégation, vous pouvez utiliser la terminologie française précise : "Un tas est un arbre tournoi quasi-complet à gauche".
Pour finir de consolider ces idées, la vidéo suivante résume la définition du tas en combinant les deux propriétés.
2.6.3 Heap - Heap Sort - Heapify - Priority Queues
Maintenant que nous avons les deux ingrédients (propriété d'ordre et structure complète), cette dernière vidéo rassemble tout pour définir ce qu'est un tas.
Regardez le segment de 14:09 à 16:18. Il définit formellement le tas ('heap') comme un arbre binaire complet qui satisfait la propriété de tas (max-heap ou min-heap).
Conclusion
Aujourd'hui, nous avons posé les fondations de la structure de tas. C'est une structure de données élégante où la géométrie (arbre complet) et l'ordre (propriété de tas) conspirent pour permettre une implémentation remarquablement efficace.
Points clés à retenir :
- Un tas binaire combine deux propriétés :
- Structure : C'est un arbre binaire quasi-complet à gauche.
- Ordre : C'est un "arbre tournoi" où chaque parent est soit plus grand (tas-max), soit plus petit (tas-min) que ses enfants.
- Cette structure permet une implémentation sans pointeurs dans un simple tableau, où la navigation se fait par des calculs d'indices.
- La racine d'un tas contient toujours l'élément extrême (maximum ou minimum), accessible en temps constant .
Prochaine étape :
Maintenant que nous savons ce qu'est un tas et comment le représenter, la question naturelle est : comment le maintenir ? Dans la prochaine leçon, nous implémenterons les opérations fondamentales d'un tas (ajouter, extraire_max/extraire_min) qui préservent ses propriétés. Ces opérations nous mèneront directement à l'implémentation du tri par tas, un algorithme de tri puissant et garanti en .