---
title: "Arbres et tri par tas"
date: "2022-03-02"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
---

# Un joli site

## Visualisation d'algorithmes

* <https://visualgo.net/>
* Allons nous rafraîchir la mémoire sur l'insertion / recherche dans un arbre
  binaire.



# Pseudocode d'insertion (1/2)

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

## Recherche du parent

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

# Pseudocode d'insertion (2/2)

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

## Ajout du fils

```
ajout(arbre, clé)
    si est_vide(arbre)
        arbre = noeud(clé)
    sinon
        arbre = position(arbre, clé)
        si clé < clé(arbre)
            gauche(arbre) = noeud(clé)
        sinon si clé > clé(arbre)
            droite(arbre) = noeud(clé)
        sinon
            retourne
```

# Code d'insertion en C (1/2)

## Recherche du parent (ensemble)

. . .

```C
tree_t position(tree_t tree, key_t key) {
    tree_t current = tree;
    if (NULL != current) {
        tree_t 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;
}
```

# Code d'insertion en C (2/2)

## Ajout du fils (ensemble)

\scriptsize

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

. . .

```C
tree_t add_key(tree_t *tree, key_t key) {
    node_t *new_node = calloc(1, sizeof(*new_node)); // nouveauté!
    new_node->key = key;
    if (NULL == *tree) {
        *tree = new_node;
    } else {
        tree_t 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;
}
```

# Une nouvelle corde à votre arc!

\footnotesize

```C
void *calloc(size_t nmemb, size_t size); // man 3 calloc
```

```
$ man 3 calloc

The calloc() function allocates memory for an array of nmemb elements
of size bytes each and returns a pointer  to  the  allocated  memory.
The  memory is set to zero.  If nmemb or size is 0, then calloc() re‐
turns either NULL, or a unique pointer value that can later  be  suc‐
cessfully  passed to free().  If the multiplication of nmemb and size
would result in integer overflow, then calloc() returns an error.  By
contrast,  an integer overflow would not be detected in the following
call to malloc(), with the result that an incorrectly sized block  of
memory would be allocated:

   malloc(nmemb * size);
```

# La suppression de clé


. . .

::: columns

:::: column

## Cas simples: 

* le noeud est absent, 
* le noeud est une feuille
* le noeuds a un seul fils.

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

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

::::

:::: 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 noeud à supprimer: utiliser `position()`.

::::

:::

# La suppression de clé


::: columns

:::: column

## Cas compliqué

* Le noeud à supprimer à (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 peut pas juste enlever `10` et recoller...
* Proposez une solution bon sang!

. . .

## 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 noeud.

::::

:::

# 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_feuill)
                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

## 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 insertion(arbre, clé)
    si est_vide(arbre)
        retourne noeud(clé)

    si (clé < arbre->clé)
        gauche(arbre) = insert(gauche(arbre), clé)
    sinon
        droite(arbre) = insert(droite(arbre), clé)
    retourne arbre
```

# Exercices (poster sur matrix)

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

. . .

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

# Exercices (à la maison)

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

# 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 set le premier élément du tableau.
* Les deux fils d'un noeud d'indice $i$, ont pour indices $2i+1$ et $2i+2$:
    * Les fils du noeud $i=0$, sont à $2\cdot 0+1=1$ et $2\cdot 0+2=2$.
    * Les fils du noeud $i=1$, sont à $2\cdot 1+1=3$ et $2\cdot 1+2=4$.
    * Les fils du noeud $i=2$, sont à $2\cdot 2+2=5$ et $2\cdot 1+2=6$.
    * Les fils du noeud $i=3$, sont à $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 noeud $i=8$ est $(8-1)/2=3$.
    * Le parent du noeud $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èche de gauche à droite, parent -> enfants.
* Les flèche 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ée" à 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/N)

```
        | 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 = 5$: `7`.
* `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/N)

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

::: columns

:::: column

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

* On continue à l'indice $N/2-1 = 4$: `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-2 = 3$: `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/N)

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

::: columns

:::: column

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

* Indice $N/2-1 = 4$: `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-2 = 3$: `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/N)

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

::: columns

:::: column

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

* Indice $N/2-3 = 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-4 = 1$: `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/N)

```
        | 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/N)

```
        | 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/N)

```
        | 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/N)

```
        | 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/N)

```
        | 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/N)

```
        | 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=400 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=400 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/N)

```
        | 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=400 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/N)

```
        | 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/N)

```
        | 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.


