Fondements de la représentation tabulaire

Contrairement aux arbres binaires de forme irrégulière qui génèrent une fragmentation importante lors d'un stockage linéaire, les arbres binaires complets se prêtent naturellement à une représentation séquentielle. En algorithmique, cette organisation est appelée tas (ou heap). Il est crucial de distinguer cette structure de contrôle des données de la zone mémoire « heap » allouée dynamiquement par le système d'exploitation, deux concepts sans lien direct.

Propriétés et variantes

Un tas impose une contrainte de valeur hiérarchique sur un arbre binaire complet. On retrouve deux modèles opposés :

• Tas maximal : chaque nœud parent détient une valeur supérieure ou égale à celles de ses enfants. La racine garantit ainsi l'accès immédiat au maximum de la collecsion.
• Tas minimal : chaque nœud parent contient une valeur inférieure ou égale à celles de ses descendants directs. La racine isole alors le minimum global.

Cette caractéristique locale permet de maintenir les valeurs extrêmes en surface, optimisant les opérations de sélection, de filtrage et de tri partiel.

Architecture logicielle en C

Pour supporter une taille dynamique, la structure encapsule un pointeur vers un tableau, un compteur d'éléments actifs et une capacité maximale. Les opérations de base reposent sur des mécanismes de rééquilibrage ascendant et descendant.

2.1 Allocation et libération des ressources

typedef struct {
    int* zone;
    size_t nb_items;
    size_t limite;
} TasDynamique;

void tas_allouer(TasDynamique* t) {
    assert(t != NULL);
    t->zone = (int*)malloc(sizeof(int) * 4);
    if (!t->zone) {
        perror("Allocation memoire echouee");
        exit(EXIT_FAILURE);
    }
    t->nb_items = 0;
    t->limite = 4;
}

void tas_detruire(TasDynamique* t) {
    free(t->zone);
    t->zone = NULL;
    t->nb_items = t->limite = 0;
}

2.2 Insertion avec rééquilibrage ascendant

L'ajout se produit toujours à la fin du tableau logique. Pour respecter l'invariant du tas maximal, l'élément introduti doit potentiellement permuter avec son nœud parent jusqu'à atteindre sa position d'équilibre ou la racine.

static void permutation(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

static void remontee(int* vect, int idx_fils) {
    int idx_parent = (idx_fils - 1) / 2;
    while (idx_fils > 0) {
        if (vect[idx_parent] < vect[idx_fils]) {
            permutation(&vect[idx_parent], &vect[idx_fils]);
            idx_fils = idx_parent;
            idx_parent = (idx_fils - 1) / 2;
        } else {
            break;
        }
    }
}

void tas_pousser(TasDynamique* t, int val) {
    assert(t != NULL);
    if (t->nb_items >= t->limite) {
        size_t nouvelle_limite = t->limite * 2;
        int* tampon = (int*)realloc(t->zone, sizeof(int) * nouvelle_limite);
        if (!tampon) {
            perror("Reallocation echouee");
            exit(EXIT_FAILURE);
        }
        t->zone = tampon;
        t->limite = nouvelle_limite;
    }
    t->zone[t->nb_items++] = val;
    remontee(t->zone, t->nb_items - 1);
}

2.3 Extraction avec rééquilibrage descendant

La suppression cible systématiquement le sommet. La technique consiste à remplacer la racine par le dernier élément du tableau, réduire la taille logique, puis propager la nouvelle valeur vers le bas en comparant avec le plus grand des enfants.

static void descente(int* vect, int taille, int idx_parent) {
    int idx_fils = idx_parent * 2 + 1;
    while (idx_fils < taille) {
        if (idx_fils + 1 < taille && vect[idx_fils] < vect[idx_fils + 1]) {
            idx_fils++;
        }
        if (vect[idx_parent] < vect[idx_fils]) {
            permutation(&vect[idx_parent], &vect[idx_fils]);
            idx_parent = idx_fils;
            idx_fils = idx_parent * 2 + 1;
        } else {
            break;
        }
    }
}

void tas_extraire(TasDynamique* t) {
    assert(t != NULL && t->nb_items > 0);
    permutation(&t->zone[0], &t->zone[t->nb_items - 1]);
    t->nb_items--;
    descente(t->zone, t->nb_items, 0);
}

int tas_sommet(const TasDynamique* t) {
    assert(t != NULL && t->nb_items > 0);
    return t->zone[0];
}

Cas d'usage algorithmiques

3.1 Initialisation d'un tas

La transformation d'un ensemble non ordonné en tas repose sur deux stratégies. L'approche naïve insère chaque élément séquentiellement avec remontée, générant une complexité en $O(n \log n)$. La méthode optimale, dite de Floyd, part du dernier nœud non-feuille et applique itérativement la descente à rebours jusqu'à l'indice zéro, atteignant une complexité linéaire $O(n)$.

void initialiser_tas(int* vect, int nb_elem) {
    for (int i = (nb_elem / 2) - 1; i >= 0; i--) {
        descente(vect, nb_elem, i);
    }
}

3.2 Tri par tas (Heapsort)

Une fois la structure maximaliste établie, le tri croissant s'obtient en extrayant cycliquement le sommet. À chaque itération, on échange la racine avec le dernier élément de la zone de traitement active, on déplace la borne vers la gauche, puis on restaure la propriété du tas sur le segment résiduel via la descente.

void trier_tas(int* vect, int nb_elem) {
    initialiser_tas(vect, nb_elem);
    int borne = nb_elem - 1;
    while (borne > 0) {
        permutation(&vect[0], &vect[borne]);
        descente(vect, borne, 0);
        borne--;
    }
}

3.3 Filtrage des K valeurs extrêmes

Lors du traitement de flux massifs ou de datasets dépassant la mémoire vive, identifier les $K$ plus grandes ou plus petites valeurs par un tri complet devient non viable. L'algorithme par tas maintient une structure de capacité fixe $K$. Pour isoler les $K$ maximums, on construit un tas minimal avec les $K$ preimers éléments. Chaque donnée suivante est comparée à la racine : si elle est plus grande, elle remplace le sommet et déclenche un rééquilibrage descendant. À l'issue du parcours, le tas contient exclusivement les $K$ plus grands éléments. La symétrie s'applique aux minimums via un tas maximal, offrant une empreinte mémoire constante $O(K)$ et une complexité temporelle optimale $O(N \log K)$.