Algorithmique · Écoles d'ingénieurs — ENSIAS

Structures de données avancées : Tas (Heaps) et Files de priorité

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

Un Tas (Heap) est un arbre binaire complet stocké dans un tableau.

Propriété de structure : Pour un nœud à l'indice $i$ , son fils gauche est à $2i+1$ et son fils droit à $2i+2$ .
Propriété de tas : Dans un Max-Heap, pour tout nœud $i$ , $A[parent(i)] \geq A[i]$ .
File de priorité : Structure permettant Insert(x) et Extract-Max().

Méthodes à maîtriser

Sift-Up (Remonter) : Utilisé lors de l'insertion. On compare l'élément avec son parent et on échange si la propriété est violée.
Sift-Down (Descendre) : Utilisé lors de la suppression. On compare le nœud avec ses fils et on échange avec le plus grand (pour Max-Heap).
Build-Heap : Construction d'un tas à partir d'un tableau non ordonné en $O(n)$ .

Exemples corrigés

Insertion de 15 dans [20, 10, 5] : On place 15 à la fin : [20, 10, 5, 15]. 15 > 10 (parent), on échange : [20, 15, 5, 10].
Extract-Max : On remplace la racine par le dernier élément, puis on fait Sift-Down.

Erreurs fréquentes

Confondre Tas et Arbre Binaire de Recherche (ABR) : Dans un tas, il n'y a pas d'ordre entre les frères.
Oublier que l'arbre doit rester complet après chaque opération.

L'essentiel du cours

Un Tas (Heap) est un arbre binaire complet stocké dans un tableau.

Propriété de structure : Pour un nœud à l'indice $i$, son fils gauche est à $2i+1$ et son fils droit à $2i+2$.
Propriété de tas : Dans un Max-Heap, pour tout nœud $i$, $A[parent(i)] \geq A[i]$.
File de priorité : Structure permettant Insert(x) et Extract-Max().

Méthodes à maîtriser

Sift-Up (Remonter) : Utilisé lors de l'insertion. On compare l'élément avec son parent et on échange si la propriété est violée.
Sift-Down (Descendre) : Utilisé lors de la suppression. On compare le nœud avec ses fils et on échange avec le plus grand (pour Max-Heap).
Build-Heap : Construction d'un tas à partir d'un tableau non ordonné en $O(n)$.

Exemples corrigés

Insertion de 15 dans [20, 10, 5] : On place 15 à la fin : [20, 10, 5, 15]. 15 > 10 (parent), on échange : [20, 15, 5, 10].
Extract-Max : On remplace la racine par le dernier élément, puis on fait Sift-Down.

Erreurs fréquentes

Confondre Tas et Arbre Binaire de Recherche (ABR) : Dans un tas, il n'y a pas d'ordre entre les frères.
Oublier que l'arbre doit rester complet après chaque opération.

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Structures de données avancées : Tas (Heaps) et Files de priorité

1/4

Quelle est la complexité de l'insertion dans un tas de taille $n$ ?

❓ Questions fréquentes

Quelle est la hauteur d'un tas avec n éléments ?

La hauteur est exactement $\lfloor \log_2 n \rfloor$ .

💡 À retenir : C'est ce qui garantit la performance des opérations.

La hauteur est exactement $\lfloor \log_2 n \rfloor$.

💡 À retenir : C'est ce qui garantit la performance des opérations.

C'est quoi la différence entre un Tas et un ABR ?

Dans un ABR, pour tout nœud, les valeurs à gauche sont plus petites et à droite plus grandes.
Dans un Tas, il n'y a pas de relation d'ordre entre les fils, seulement entre le parent et ses fils.

💡 À retenir : Le Tas est optimisé pour trouver le max/min, l'ABR pour la recherche d'une valeur spécifique.

Kifach n7seb l'indice dyal l'parent f tableau ?

Si l'indice du nœud est $i$ (en commençant par 0) :

L'indice du parent est donné par la formule : $parent = \lfloor \frac{i-1}{2} \rfloor$ .

💡 À retenir : La division entière est cruciale pour trouver le parent.

Si l'indice du nœud est $i$ (en commençant par 0) :

L'indice du parent est donné par la formule : $parent = \lfloor \frac{i-1}{2} \rfloor$.

💡 À retenir : La division entière est cruciale pour trouver le parent.

Chno hiya l'complexité dyal Extract-Max ?

On remplace la racine par la dernière feuille : $O(1)$ .
On effectue Sift-Down sur la hauteur de l'arbre : $O(\log n)$ .

💡 À retenir : La complexité est logarithmique car la hauteur d'un arbre complet est $\log n$ .

On remplace la racine par la dernière feuille : $O(1)$.
On effectue Sift-Down sur la hauteur de l'arbre : $O(\log n)$.

💡 À retenir : La complexité est logarithmique car la hauteur d'un arbre complet est $\log n$.

Wach l'tas kaytkhdem ghir b les tableaux ?

Oui, car le stockage dans un tableau permet un accès direct aux fils et parents via des calculs d'indices, ce qui est très efficace en mémoire.

💡 À retenir : L'utilisation d'un tableau évite les pointeurs coûteux.

Est-ce que le Build-Heap est toujours en O(n log n) ?

Non, une construction naïve est en $O(n \log n)$ , mais en utilisant l'algorithme de Floyd (bottom-up), on atteint $O(n)$ .

💡 À retenir : $O(n)$ est la complexité optimale pour construire un tas.

Non, une construction naïve est en $O(n \log n)$, mais en utilisant l'algorithme de Floyd (bottom-up), on atteint $O(n)$.

💡 À retenir : $O(n)$ est la complexité optimale pour construire un tas.

Kifach n3ref wach l'tas li 3ndi Max-Heap aw Min-Heap ?

Regarde la racine : si c'est la valeur maximale, c'est un Max-Heap.
Si c'est la valeur minimale, c'est un Min-Heap.

💡 À retenir : La racine est toujours l'élément extrême (max ou min).

Est-ce qu'un tableau trié est toujours un Tas ?

Oui, un tableau trié par ordre croissant est un Min-Heap valide, mais l'inverse n'est pas vrai.

💡 À retenir : Un tas est une condition plus faible qu'un tri complet.

Pourquoi on utilise Sift-Down après Extract-Max ?

Parce qu'en remplaçant la racine par la dernière feuille, on viole probablement la propriété de tas. Il faut "descendre" cette valeur pour rétablir l'ordre.

💡 À retenir : Sift-Down rétablit la propriété de tas localement.

Peut-on supprimer un élément autre que la racine ?

Oui, mais c'est complexe : il faut remplacer l'élément par la dernière feuille, puis faire soit Sift-Up soit Sift-Down selon la valeur.

💡 À retenir : L'opération standard est Extract-Max, les autres sont des variantes.

Est-ce que le Tas est une structure stable ?

Non, le Tas n'est pas une structure stable car les échanges lors du Sift-Down peuvent modifier l'ordre relatif des éléments égaux.

💡 À retenir : La stabilité n'est pas une propriété requise pour les files de priorité.

Chno l'far9 bin Heapify et Build-Heap ?

Heapify est l'opération qui maintient la propriété sur un sous-arbre.
Build-Heap est l'application répétée de Heapify sur tout le tableau.

💡 À retenir : Heapify est la brique de base de Build-Heap.

✍️ Exercices type examen national

Exercice 1

Soit le tableau $T = [10, 12, 1, 14, 6, 5, 8]$ . Construire le Max-Heap correspondant en utilisant l'algorithme de construction bottom-up.

Exercice 1

Soit le tableau $T = [10, 12, 1, 14, 6, 5, 8]$. Construire le Max-Heap correspondant en utilisant l'algorithme de construction bottom-up.

Voir la correction détaillée : inscription gratuite

Exercice 2

Donner l'état du Max-Heap $[20, 15, 10, 5, 12]$ après l'insertion de la valeur 18.

Exercice 2

Donner l'état du Max-Heap $[20, 15, 10, 5, 12]$ après l'insertion de la valeur 18.

Voir la correction détaillée : inscription gratuite

Exercice 3

Expliquer pourquoi la complexité de Extract-Max est $O(\log n)$ .

Exercice 3

Expliquer pourquoi la complexité de Extract-Max est $O(\log n)$.

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Algorithmique

Introduction à l'algorithmique et complexité Structures de données linéaires : Listes, Piles et Files Récursivité et méthodes de conception d'algorithmes Algorithmes de tri et de recherche Arbres binaires et arbres de recherche Tables de hachage (Hash Tables)Graphes : Représentations et parcours (BFS, DFS)Algorithmes sur les graphes : Plus courts chemins et arbres couvrants Programmation dynamique Algorithmes gloutons Introduction à la théorie de la complexité (P vs NP)