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;
}

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

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 :

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 :

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 ?

1/10

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é

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 ?

1/12

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

La racine est vide.

On remplace 10 à la racine .

i=0;

i=0, j=1;

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

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

i=1;

i=1, j=3;

On compare les valeurs de nœuds i et j : 10 et 80

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

i=3;

i=3, j=8;

On compare les valeurs de nœuds i et j : 10 et 40

On échange le contenu des nœuds d'indice 3 et 8

i=8;

C'est une feuille et c'est un tas

On quitte la boucle

5.3 Complexité