---
title: "Arbres binaires, tri par tas"
date: "2025-03-14"
---

# Les arbres binaires

\Huge Les arbres binaires

# Rappel pour l'insertion

* Les éléments insérés ont une notion d'ordre
* On parcourt l'arbre jusqu'à pouvoir ajouter une nouvelle feuille

# Pseudo-code d'insertion (1/4)

\footnotesize

* Deux parties:
    * Recherche le parent où se passe l'insertion.
    * Ajout de l'enfant dans l'arbre.

## Recherche du parent

```python
arbre position(tree, clé)
    si est_non_vide(tree)
        si clé < clé(tree)
            suivant = gauche(tree)
        sinon
            suivant = droite(tree)
        tant que clé(tree) != clé && est_non_vide(suivant)
            tree = suivant
            si clé < clé(tree)
                suivant = gauche(tree)
            sinon
                suivant = droite(tree)
            
    retourne tree
```

# Pseudo-code d'insertion (2/4)

* Deux parties:
    * Recherche de la position.
    * Ajout dans l'arbre.

## Ajout de l'enfant

```
rien ajout(tree, clé)
    si est_vide(tree)
        tree = nœud(clé)
    sinon
        si clé < clé(tree)
            gauche(tree) = nœud(clé)
        sinon si clé > clé(tree)
            droite(tree) = nœud(clé)
        sinon
            retourne
```

# Code d'insertion en C

## Recherche du parent (ensemble)

. . .

```C
node *position(node *tree, key_t key) {
    node * current = tree;
    if (NULL != current) {
        node *subtree = key > current->key 
                        ? current->right : current->left;
        while (key != current->key && NULL != subtree) {
            current = subtree;
            subtree = key > current->key 
                      ? current->right : current->left;
        }
    }
    return current;
}
```

# L'insertion (3/4)

* Deux parties:
    * Recherche de la position.
    * Ajout dans l'arbre.

## Ajout du fils (pseudo-code)

```
rien ajout(tree, clé)
    si est_vide(tree)
        tree = nœud(clé)
    sinon
        tree = position(tree, clé)
        si clé < clé(tree)
            gauche(tree) = nœud(clé)
        sinon si clé > clé(tree)
            droite(tree) = nœud(clé)
        sinon
            retourne
```



# L'insertion (4/4)

## Ajout du fils (code)

\scriptsize

* 2 cas: arbre vide ou pas.
* on retourne un pointeur vers le nœud ajouté (ou `NULL`)

. . .

```C
node *add_key(node **tree, key_t key) {
    node *new_node = calloc(1, sizeof(*new_node));
    new_node->key = key;
    if (NULL == *tree) {
        *tree = new_node;
    } else {
        node * subtree = position(*tree, key);
        if (key == subtree->key) {
            return NULL;
        } else {
            if (key > subtree->key) {
                subtree->right = new_node;
            } else {
                subtree->left = new_node;
            }
        }
    }
    return new_node;
}
```

# La suppression dans un arbre binaire

\Huge La suppression dans un arbre binaire

# La suppression de clé

::: columns

:::: column

## Cas simples: 

* le nœud est absent, 
* le nœud est une feuille,
* le nœuds a un seul fils.

## Une feuille (le 19 p.ex.).

```{.mermaid format=pdf width=150 loc=figs/}
flowchart TB;
    10-->20;
    10-->5
    20-->19
    20-->21
```

::::

:::: column

## Un seul fils (le 20 p.ex.).

```{.mermaid format=pdf width=400 loc=figs/}
flowchart TB;
    10-->20;
    10-->5
    20-->25
    20-->18
    25-->24
    25-->30
    5-->4;
    5-->8;
    style 18 fill:#fff,stroke:#fff,color:#fff
```

## Dans tous les cas

* Chercher le nœud à supprimer: utiliser `position()`.

::::

:::

# La suppression de clé


::: columns

:::: column

## Cas compliqué

* Le nœud à supprimer a (au moins) deux descendants (10).

```{.mermaid format=pdf width=400 loc=figs/}
flowchart TB;
    10-->20;
    10-->5
    20-->25
    20-->18
    25-->24
    25-->30
    5-->4;
    5-->8;
```

::::

:::: column

* Si on enlève 10, il se passe quoi?

. . .

* On ne peut pas juste enlever `10` et recoller...
* Proposez une solution !

. . .

## Solution

* Échange de la valeur à droite dans le sous-arbre de gauche ou ...
* de la valeur de gauche dans le sous-arbre de droite!
* Puis, on retire le nœud.

::::

:::

# Le pseudo-code  de la suppression

## Pour une feuille ou absent (ensemble)

```
arbre suppression(arbre, clé)
    sous_arbre = position(arbre, clé)
    si est_vide(sous_arbre) ou clé(sous_arbre) != clé
        retourne vide
    sinon
        si est_feuille(sous_arbre) et clé(sous_arbre) == clé
            nouvelle_feuille = parent(arbre, sous_arbre)
            si est_vide(nouvelle_feuille)
                arbre = vide
            sinon 
                si gauche(nouvelle_feuille) == sous_arbre 
                    gauche(nouvelle_feuille) = vide
                sinon
                    droite(nouvelle_feuille) = vide
        retourne sous_arbre
```

# Il nous manque le code pour le `parent`

## Pseudo-code pour trouver le parent (5min -> matrix)

. . .

```
arbre parent(arbre, sous_arbre)
    si est_non_vide(arbre)
        actuel = arbre
        parent = actuel
        clé = clé(sous_arbre)
        faire
            si (clé != clé(actuel))
                parent = actuel
                si clé < clé(actuel)
                    actuel = gauche(actuel)
                sinon
                    actuel = droite(actuel)
            sinon
                retour parent
        tant_que (actuel != sous_arbre)
    retourne vide
```

# Le pseudo-code  de la suppression

\footnotesize

## Pour un seul enfant (5min -> matrix)

. . .

```
arbre suppression(arbre, clé)
    sous_arbre = position(arbre, clé)
    si est_vide(gauche(sous_arbre)) ou est_vide(droite(sous_arbre))
        parent = parent(arbre, sous_arbre)
        si est_vide(gauche(sous_arbre))
            si droite(parent) == sous_arbre
                droite(parent) = droite(sous_arbre)
            sinon
                gauche(parent) = droite(sous_arbre)
        sinon
            si droite(parent) == sous_arbre
                droite(parent) = gauche(sous_arbre)
            sinon
                gauche(parent) = gauche(sous_arbre)
        retourne sous_arbre
```


# Le pseudo-code  de la suppression

\footnotesize

## Pour au moins deux enfants (ensemble)

```
arbre suppression(arbre, clé)
    sous_arbre = position(arbre, clé) # on revérifie pas que c'est bien la clé
    si est_non_vide(gauche(sous_arbre)) et est_non_vide(droite(sous_arbre))
        max_gauche = position(gauche(sous_arbre), clé)
        échange(clé(max_gauche), clé(sous_arbre))
        suppression(gauche(sous_arbre), clé)
```


# Exercices (poster sur matrix)

1. Écrire le pseudo-code de l'insertion purement en récursif.

. . .

```
arbre insert(tree, clé)
    si est_vide(tree)
        retourne nœud(clé)

    si (clé < tree(clé))
        gauche(tree) = insert(gauche(tree), clé)
    sinon
        droite(tree) = insert(droite(tree), clé)
    retourne tree
```

# Exercices (poster sur matrix)

2. Écrire le pseudo-code de la recherche purement en récursif.

. . .

```
booléen recherche(tree, clé)
    si est_vide(tree)
        retourne faux // pas trouvée
    si clé(tree) == clé
        retourne vrai // trouvée
    si clé < clé(tree)
        retourne recherche(gauche(tree), clé)
    sinon
        retourne recherche(droite(tree), clé)
```

# Exercices (à la maison)

3. Écrire une fonction qui insère des mots dans un arbre et ensuite affiche l'arbre.

# Le tri par tas

\Huge Le tri par tas

# Trier un tableau à l'aide d'un arbre binaire

* Tableau représenté comme un arbre binaire.
* Aide à comprendre "comment" trier, mais on ne construit jamais l'arbre.
* Complexité $O(N\log_2 N)$ en moyenne et grande stabilité (pas de cas
  dégénérés).

# Lien entre arbre et tableau

* La racine de l'arbre est le premier élément du tableau.
* Les deux fils d'un nœud d'indice $i$, ont pour indices $2i+1$ et $2i+2$:
    * Les fils du nœud $i=0$ sont en $2\cdot 0+1=1$ et $2\cdot 0+2=2$.
    * Les fils du nœud $i=1$ sont en $2\cdot 1+1=3$ et $2\cdot 1+2=4$.
    * Les fils du nœud $i=2$ sont en $2\cdot 2+2=5$ et $2\cdot 1+2=6$.
    * Les fils du nœud $i=3$ sont en $2\cdot 3+1=7$ et $2\cdot 3+2=8$.
* Un élément d'indice $i$ a pour parent l'élément $(i-1)/2$ (division entière):
    * Le parent du nœud $i=8$ est $(8-1)/2=3$.
    * Le parent du nœud $i=7$ est $(7-1)/2=3$.

# Visuellement

::: columns

:::: column

* Où vont les indices correspondant du tableau?

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0(( ))-->id1(( ));
    id0-->id2(( ));
    id1-->id3(( ));
    id1-->id4(( ));
    id2-->id5(( ));
    id2-->id6(( ));
    id3-->id7(( ));
    id3-->id8(( ));
    id4-->id9(( ));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```
::::

:::: column

* Les flèches de gauche à droite, parent -> enfants.
* Les flèches de droite à gauche, enfants -> parent.

![Dualité tableau arbre binaire.](figs/heap_tree.svg)

::::

:::

**Propriétés:** 

1. les feuilles sont toutes sur l'avant dernier ou dernier niveau.
2. les feuilles de profondeur maximale sont "tassées" à gauche.

# Le tas (ou heap)

## Définition

* Un arbre est un tas, si la valeur de chacun de ses descendants est inférieure
  ou égale à sa propre valeur.

## Exemples (ou pas)

```
16  8 14 6 2 10 12 4 5 # Tas
16 14  8 6 2 10 12 4 5 # Non-tas, 10 > 8 et 12 > 8
```

## Exercices (ou pas)

```
19 18 12 12 17 1 13 4 5 # Tas ou pas tas?
19 18 16 12 17 1 12 4 5 # Tas ou pas tas?
```

. . .

```
19 18 12 12 17 1 13 4 5 # Pas tas! 13 > 12
19 18 16 12 17 1 12 4 5 # Tas!
```

# Exemple de tri par tas (1/13)

```
        | 1 | 16 | 5 | 12 | 4 | 2 | 8 | 10 | 6 | 7 |
```

::: columns

:::: column

* Quel est l'arbre que cela représente?

. . .

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((7));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Transformer l'arbre en tas.

* On commence à l'indice $N/2-1 = 4$: `4`.
* `7 > 4` (enfant `>` parent).
* intervertir `4` et `7`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::

. . .

```
                            *                    *
        | 1 | 16 | 5 | 12 | 7 | 2 | 8 | 10 | 6 | 4 |
```

# Exemple de tri par tas (2/13)

```
        | 1 | 16 | 5 | 12 | 7 | 2 | 8 | 10 | 6 | 4 |
```

::: columns

:::: column

**But:** Transformer l'arbre en tas.

* On continue à l'indice $N/2-2 = 3$: `12`.
* Déjà un tas, rien à faire.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Transformer l'arbre en tas.

* On continue à l'indice $N/2-3 = 2$: `5`.
* `5 < 8`, échanger `8` et `5` (aka `max(2, 5, 8)`)

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((16));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::

. . .

```
        | 1 | 16 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |
```

# Exemple de tri par tas (3/13)

```
        | 1 | 16 | 5 | 12 | 7 | 2 | 8 | 10 | 6 | 4 |
```

::: columns

:::: column

**But:** Transformer l'arbre en tas.

* Indice $N/2-2 = 3$: `12`.
* Déjà un tas, rien à faire.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Transformer l'arbre en tas.

* Indice $N/2-3 = 2$: `5`.
* `5 < 8`, `5 <=> max(2, 5, 8)`

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((16));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::

```
                   *                *
        | 1 | 16 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |
```

# Exemple de tri par tas (4/13)

```
        | 1 | 16 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |
```

::: columns

:::: column

**But:** Transformer l'arbre en tas.

* Indice $N/2-4 = 1$: `16`.
* Déjà un tas, rien à faire.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((16));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Transformer l'arbre en tas.

* Indice $N/2-5 = 0$: `1`.
* `1 < 16 && 1 < 8`, `1 <=> max(1, 16, 8)`

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((16))-->id1((1));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::

```
           *   *
        | 16 | 1 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |
```


# Exemple de tri par tas (5/13)

```
        | 16 | 1 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |
```

::: columns

:::: column

**But:** Transformer l'arbre en tas.

* Recommencer avec `1`.
* `1 <=> max(1, 12, 7)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((16))-->id1((12));
    id0-->id2((8));
    id1-->id3((1));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Transformer l'arbre en tas.

* Recommencer avec `1`.
* `1 <=> max(1, 10, 6)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((16))-->id1((12));
    id0-->id2((8));
    id1-->id3((10));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff
```

::::

:::

```
                *        *               *
        | 16 | 12 | 8 | 10 | 7 | 2 | 5 | 1 | 6 | 4 |
```

* L'arbre est un tas.

# Exemple de tri par tas (6/13)

```
        | 16 | 12 | 8 | 10 | 7 | 2 | 5 | 1 | 6 | 4 |
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `16` (`max` de l'arbre) avec `4`.
* Traiter la racine.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((4))-->id1((12));
    id0-->id2((8));
    id1-->id3((10));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((6));
```

::::

:::: column

**But:** Trier les tas.

* `4 <=> max(4, 12, 8)`.
* `4 <=> max(4, 10, 7)`.
* `4 <=> max(4, 1, 6)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((12))-->id1((10));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((4));
```

::::

:::

```
        | 12 | 10 | 8 | 6 | 7 | 2 | 5 | 1 | 4 || 16
```


# Exemple de tri par tas (7/13)

```
        | 12 | 10 | 8 | 6 | 7 | 2 | 5 | 1 | 4 || 16
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `12` (`max` de l'arbre) avec `4`.
* Traiter la racine.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((4))-->id1((10));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((  ));
    style id8 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Trier les tas.

* `4 <=> max(4, 10, 8)`.
* `4 <=> max(4, 6, 7)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((10))-->id1((7));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((  ));
    style id8 fill:#fff,stroke:#fff
```

::::

:::

```
        | 10 | 7 | 8 | 6 | 4 | 2 | 5 | 1 || 12 | 16
```

# Exemple de tri par tas (8/13)

```
        | 10 | 7 | 8 | 6 | 4 | 2 | 5 | 1 || 12 | 16
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `10` (`max` de l'arbre) avec `1`.
* Traiter la racine.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((7));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((5));
```

::::

:::: column

**But:** Trier les tas.

* `1 <=> max(1, 7, 8)`.
* `5 <=> max(1, 2, 5)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((8))-->id1((7));
    id0-->id2((5));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((1));
```

::::

:::

```
        | 8 | 7 | 5 | 6 | 4 | 2 | 1 || 10 | 12 | 16
```

# Exemple de tri par tas (9/13)

```
        | 8 | 7 | 5 | 6 | 4 | 2 | 1 || 10 | 12 | 16
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `8` (`max` de l'arbre) avec `1`.
* Traiter la racine.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((7));
    id0-->id2((5));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((  ));
    style id6 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Trier les tas.

* `1 <=> max(1, 7, 5)`.
* `1 <=> max(1, 6, 4)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((7))-->id1((6));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((  ));
    style id6 fill:#fff,stroke:#fff
```

::::

:::

```
        | 7 | 6 | 5 | 1 | 4 | 2 || 8 | 10 | 12 | 16
```

# Exemple de tri par tas (10/13)

```
        | 7 | 6 | 5 | 1 | 4 | 2 || 8 | 10 | 12 | 16
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `7` (`max` de l'arbre) avec `2`.
* Traiter la racine.

```{.mermaid format=pdf width=150 loc=figs/}
graph TD;
    id0((2))-->id1((6));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((4));
```

::::

:::: column

**But:** Trier les tas.

* `2 <=> max(2, 6, 5)`.
* `2 <=> max(2, 1, 4)`.

```{.mermaid format=pdf width=150 loc=figs/}
graph TD;
    id0((6))-->id1((4));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((2));
```

::::

:::

```
        | 6 | 4 | 5 | 1 | 2 || 8 | 10 | 12 | 16
```

# Exemple de tri par tas (11/13)

```
        | 6 | 4 | 5 | 1 | 2 || 8 | 10 | 12 | 16
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `6` (`max` de l'arbre) avec `2`.
* Traiter la racine.

```{.mermaid format=pdf width=150 loc=figs/}
graph TD;
    id0((2))-->id1((4));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((  ));
    style id4 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Trier les tas.

* `2 <=> max(2, 4, 5)`.
* `2 <=> max(2, 1, 4)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((5))-->id1((4));
    id0-->id2((2));
    id1-->id3((1));
    id1-->id4((  ));
    style id4 fill:#fff,stroke:#fff
```

::::

:::

```
        | 5 | 4 | 2 | 1 || 6 | 8 | 10 | 12 | 16
```

# Exemple de tri par tas (12/13)

```
        | 5 | 4 | 2 | 1 || 6 | 8 | 10 | 12 | 16
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `5` (`max` de l'arbre) avec `1`.
* Traiter la racine.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((1))-->id1((4));
    id0-->id2((2));
```

::::

:::: column

**But:** Trier les tas.

* `1 <=> max(1, 4, 2)`.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((4))-->id1((1));
    id0-->id2((2));
```

::::

:::

```
        | 4 | 1 | 2 || 5 | 6 | 8 | 10 | 12 | 16
```

# Exemple de tri par tas (13/13)

```
        | 4 | 1 | 2 || 5 | 6 | 8 | 10 | 12 | 16
```

::: columns

:::: column

**But:** Trier les tas.

* Échanger la racine, `4` (`max` de l'arbre) avec `2`.
* Traiter la racine.

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((2))-->id1((1));
    id0-->id2(( ));
    style id2 fill:#fff,stroke:#fff
```

::::

:::: column

**But:** Trier les tas. Plus rien à trier

* On fait les 2 dernières étapes en vitesse.
* Échange `2` avec `1`.
* Il reste que `1`. GGWP!


::::

:::

```
        | 1 | 2 | 4 | 5 | 6 | 8 | 10 | 12 | 16
```

# Exercice (10min)

* Trier par tas le tableau

```
        | 1 | 2 | 4 | 5 | 6 | 8 | 10 | 12 | 16
```

* Mettez autant de détails que possible.
* Que constatez-vous?
* Postez le résultat sur matrix.

# L'algorithme du tri par tas (1/2)

\footnotesize

## Deux étapes

1. Entassement: transformer l'arbre en tas.
2. Échanger la racine avec le dernier élément et entasser la racine.

## Pseudo-code d'entassement de l'arbre (15 min, matrix)

. . .

```python
rien tri_par_tas(tab)
    entassement(tab)
    échanger(tab[0], tab[size(tab)-1])
    pour i de size(tab)-1 à 2 
        tamisage(tab, 0)
        échanger(tab[0], tab[i-1])

rien entassement(tab)
    pour i de size(tab)/2-1 à 0
        tamisage(tab, i)

rien tamisage(tab, i)
    ind_max = ind_max(tab, i, gauche(i), droite(i))
    si i != ind_max
        échanger(tab[i], tab[ind_max])
        tamisage(tab, ind_max)
```

# L'algorithme du tri par tas (2/2)

* Fonctions utilitaires

    ```python
    entier ind_max(tab, i, g, d)
        ind_max = i
        si g < size(tab) && tab[ind_max] < tab[g] 
            ind_max = g
        si d < size(tab) > d && tab[ind_max] < tab[d]
            ind_max = d
        retourne ind_max

    entier gauche(i)
        retourne 2 * i + 1
    
    entier droite(i)
        retourne 2 * i + 2
    ```


<!-- # L'algorithme du tri par tas (3/4)

\footnotesize

## Implémenter en C l'algorithme du tri par tas (matrix, 20min)

. . .

```C 
void heapsort(int size, int tab[size]) {
    heapify(size, tab);
    swap(tab, tab + size - 1);
    for (int s = size - 1; s > 1; s--) {
        sift_up(s, tab, 0);
        swap(tab, tab + s - 1);
    }
}
void heapify(int size, int tab[size]) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        sift_up(size, tab, i);
    }
}
void sift_up(int size, int tab[size], int i) {
    int ind_max = ind_max3(size, tab, i, left(i), right(i));
    if (i != ind_max) {
        swap(tab + i, tab + ind_max);
        sift_up(size, tab, ind_max);
    }
}
```

# L'algorithme du tri par tas (4/4)

\footnotesize

## Fonctions utilitaires

. . .

```C
int ind_max3(int size, int tab[size], int i, int l, int r) {
    int ind_max = i;
    if (l < size && tab[ind_max] < tab[l]) {
        ind_max = l;
    }
    if (r < size && tab[ind_max] < tab[r]) {
        ind_max = r;
    }
    return ind_max;
}
void swap(int *a, int *b) {
    int tmp = *a;
    *a      = *b;
    *b      = tmp;
}
int left(int i) {
    return 2 * i + 1;
}
int right(int i) {
    return 2 * i + 2;
}
``` -->


