Projet ZZ1 : Labyrinthe

Tas binaire

Implémentation

Nous avons implémenter un tas binaire afin de pouvoir gérer une file de priorité comme suit :

  • La racine porte la valeur maximale
  • L'arbre est représenté sous forme de tableau (car un tas est un arbre binaire complet)
  • Le père d'un noeud i est à l'indice (i-1)/2
  • Le fils gauche d'un noeud i est à l'indice 2*i+1
  • Le fils droit d'un noeud i est à l'indice 2*i+2

    • Fonctions

  • Tout d'abord la fonction pour insérer une valeur dans le tas :

    •     int enfiler (tas_t * tas, int val);

    Le principe général est d'insérer la valeur à la fin de l'arbre puis de la faire remonter à la bonne place. Cependant pour cette fonction on a fait le choix d'insérer une fois la bonne place atteinte après avoir réorganisé le tas. La fonction retourne 0 si tout s'est bien passé et -1 sinon.

    Compléxité : Θ(log(N))

  • La fonction suivante permet de supprimer la priorité la plus élevée :

    •     int defiler (tas_t * tas);

    Cette valeur correspond à la racine. Il faut donc supprimer la racine puis faire remonter les valeurs en dessous. Dans la pratique, la valeur de la racine a juste besoin d'etre stockée afin de la récupérée car on va simplement écraser les valeurs à chaque noeud modifié. La fonction retourne donc la priorité la plus élevée si tout s'est bien passé et -1 sinon.

    Compléxité : Θ(log(N))

  • Pour transformer un tableau en tas :

    •     tas_t * tabToTas (int * T, int taille);

    Cette fonction a pour but de transformer nimporte quel tableau d'entiers en un tas. Elle utilise la fonction void entasser (tas_t * tas, int i); qui permet de réorganiser une valeur dans un arbre en descendant. La méthode pour le tri par tas est la suivante : on laisse de coté les feuilles et pour chaque noeud i de (taille-1)/2 à 0, on appelle la fonction entasser.

    Compléxité : Θ(N x log(N))

    Tri par tas

        void triParTas (tas_t * tas);

    Le principe du tri par tas est simple, on sait que la valeur maximale est au niveau de la racine. On échange la racine avec l'élément à la case i (le dernier élément du tas à l'initialisation) puis on entasse de la case 1 à i. On recommence l'opération en diminuant i de 1 à chaque fois jusqu'à 1.

    Compléxité : Θ(N x log(N))

    Comparaison avec qsort

    Pour un tableau de taille 100 000 constuit tel que la case d'indice i contienne la valeur i, on obtient les temps d'exécutions suivant :

  • Avec notre algorithme de tri par tas : 0.020407 secondes
  • Avec la fonction qsort de la librairie standard : 0.002076 secondes