Tas et Tri

Cette fiche introduit la notion et la réalisation du type abstrait Heap, appelé en Français "Tas" et du tri par tas.

Cette fiche introduit un type particulier d'arbre, les arbres binaires parfaits, qui sont facilement représentés par des tableaux. Le TAS est un arbre complet dont la propriété essentielle permet de trouver facilement le plus grand élément d'un ensemble. Cette structure de données est utilisée dans le tri par tas ou les files de priorités.

1. Qu'est ce qu'un tas ?

1.1 Trouver un maximum

Dans de nombreux algorithmes, il est nécessaire de trouver rapidement le plus grand (resp. petit) élément d'un ensemble. L'algorithme le plus simple consiste bien sûr à parcourir le tableau en comparant l'élément du tableau au maximum courant et à modifier ce maximum s'il est plus petit que l’élément courant.

              
              // Recherche du maximum d'un tableau de reels
              // PRECONDITION : tableau non vide ie n > 0
              double array_amx(double * tab, int n) {
                int i;
                double max = tab[0];
                for (i=1; i < n; i++)
                  if (max < tab[i])
                      max = tab[i];
                return max;
              }

Quelle est la complexité de cette solution ?

O(1) ? Non, tous les éléments du tableau sont parcourus au moins une fois.

O(n) ? Oui, tous les éléments du tableau sont parcourus une fois et une seule.

O(n.ln(n)) Non, tous les éléments du tableau sont parcourus au plus une fois.

O(n^2) Non, tous les éléments du tableau sont parcourus au plus une fois.

Les éléments sont examinés une fois et une seule, soit O(n). Mais il existe des structures de données plus efficaces : le TAS.

La structure de tas va permettre des opérations en O(ln(n))

Un TAS est :

un arbre binaire parfait : tous les niveaux de l'arbre sont remplis par des éléments sauf le dernier
chaque élément de l'arbre est plus grand (resp. petit) que son sous arbre droit ET que son sous arbre gauche.

Propriété essentielle
le plus grand (resp. petit) élément est la racine.

1.2 Un exemple de TAS avec des entiers

Pour chaque nœud de l'arbre, la propriété "le nœud est plus grand que les 2 fils" est bien vérifiée.

2. Représentation d'un arbre parfait

Nous pouvons bien sûr représenter les arbres avec des structures chaînées récursives comme les listes : un nœud contient une donnée et l'adresse des ses fils.

Dans le cas des arbres parfaits, tous les niveaux de l'arbre sont remplis sauf le dernier. Nous allons pouvoir utiliser une représentation par tableau en remarquant les relations existantes entre les indices d'un tableau et la numérotation des nœuds suivante :

Ici, chaque nœud contient l'indice du tableau le représentant.

Avec cette numérotation, l'arbre précédent se représente avec le tableau suivant:

Un des intérêts de cette représentation et cette numérotation sont les relations qui relient les indices d'un père ou les fils d'un nœud au sein de ce tableau. Il est facile d'accéder aux fils d'un noeud, comme dans le cas des structures chaînées, mais il est aussi facile d'accéder au père d'un noeud.

Les relations entre les indices des pères et des fils d'un noeud d'indice i sont les suivantes :

pere(i)=(i-1)/2
fils_gauche(i)=2*i+1
fils_droit(i)=2*(i+1)

3. Le TAD `heap_t`

On suppose que le type element_t désigne le type des valeurs du tas.

Pour définir notre type tas, nous allons utiliser une structure qui contiendra à la fois les données, la taille maximale du tableau et le nombre actuel d'éléments dans le tas. Ce tableau devra donc être alloué dynamiquement. Sa définition est la suivante :

            
              typedef
                  struct {
                    element_t* data; // Tableau alloué dynamiquement d'éléments
                    int max_size;    // Nombre maximal d'éléments
                    int number;      // Nombre actuel d'éléments
                  } heap_t;

Avec cette définition, l'interface minimale de ce type de données est la suivante :

Interface minimale en C du type abstrait TAS :

prototype	contrat
`heap_t heap_new(int m)`	crée et retourne un tas de `m` éléments au maximum;
`int heap_is_empty(heap_t tas)`	retourne `true (1)` si le tas est vide et `false (0)` sinon.
`int heap_add(element_t valeur, heap_t* ptas)`	ajoute l'élément `valeur` au tas pointé par le paramètre `ptas`. Cet ajout provoque la réorganisation du tas pour maintenir sa propriété essentielle Retourne `true (1)` si réussi et `false (0)` sinon.
`element_t heap_get_max(heap_t tas)`	retourne l'élément le plus grand, c'est-à-dire la racine
`int heap_delete_max(heap_t* ptas)`	Supprime l'élément le plus grand (la racine) du tas pointé par `ptas` , met le dernier élément du tas à sa place et réorganise le tas pour maintenir sa propriété essentielle. Retourne `true (1)` si réussi et `false (0)` sinon.
`heap_t heap_delete(heap_t t)`	supprime tous les éléments, détruit la table et retourne une table vide

4. Ajout d'un élément dans un tas

4.1 Principe

pour ajouter un élément dans un tas, on l'ajoute à la première place libre de l'arbre

Puis, on remonte cet élément vers la racine en l'échangeant avec son père si l'ordre entre le père et le fils n'est pas respecté (le père est plus grand que le fils)

On s’arrête soit à la racine, soit quand l'ordre entre le père et le fils est respecté

4.2 Algorithme et exemple

Comment ajouter 150 au tas précédent ?


                i=indice du dernier élément+1
                mettre l'élément à ajouter dans cette case de tableau
                tant que i n'est pas la racine (i==0)
                  j = indice du pere de i
                  si la valeur du nœud j est plus petite que la valeur du nœud i
                  alors
                    // Les nœuds ne sont pas dans le bon ordre,
                    // ce n'est pas encore un tas
                    echanger les valeurs des nœuds j et i
                    i = j
                  sinon
                    // Les nœuds sont dans le bon ordre, c'est un tas
                    Sortir de la boucle

On ajoute 150 en fin d'arbre

i=10;

i=10, j=4;

On compare les valeurs de nœuds i et j : 150 et 70 ?

On échange le contenu des nœuds d'indice 10 et 4

i=4;

i=4, j=1;

On compare les valeurs de nœuds i et j : 150 et 140 ?

On échange le contenu des nœuds d'indice 4 et 1

i=1;

i=1, j=0;

On compare les valeurs de nœuds i et j : 150 et 160 ?

Les nœuds d'indices 1 et 0 respectent l'ordre : c'est un tas

On quitte la boucle

4.3 Complexité

Quelle est la complexité de cette solution ?

O(1) ? Non, plusieurs éléments du tableau sont parcourus au moins une fois.

O(ln(n)) ? Oui, seule une branche de l'arbre est parcourue. La taille maximale d'une branche est ln(n).

O(n) Non, les éléments du tableau NE sont PAS tous parcourus une fois.

Seule une branche est parcourue : on est donc en 0(ln(n)).

5. Suppression de la racine d'un tas

5.1 Principe

Le tas permet de trouver facilement le maximum puisque c'est la racine de l'arbre. La plupart des algorithmes récupèrent cette valeur et la supprime du tas. La racine est alors vide et la structure n'est plus un tas.

Pour réorganiser le tas, on remplace la racine par le dernier élément de l'arbre.

Puis, on descend cet élément vers les feuilles en l'échangeant avec le plus grand de ses deux fils si l'ordre entre le père et le fils n'est pas respecté (le père est plus grand que le fils).

On s’arrête soit sur une feuille (pas de fils), soit quand l'ordre entre le père et le fils est respecté.

5.2 Algorithme et exemple

Suppression de 160 dans le tas précédent ?


                i= indice de la racine =0
                suppression de la valeur à la racine
                mettre le dernier élément élément à la racine
                tant que i n'est pas une feuille
                  j = indice du plus grand des fils de i
                  // Attention : i peut avoir 1 ou 2 fils
                  si la valeur du nœud d'indice j est plus grande que la valeur du nœud i
                  alors
                    // Les nœuds ne sont pas dans le bon ordre,
                    // ce n'est pas encore un tas
                    echanger les valeurs des nœuds j et i
                    i = j
                  sinon
                    // Les nœuds sont dans le bon ordre, c'est un tas
                    Sortir de la boucle

On supprime 160 à la racine