Tri par Tas

On manipule une nouvelle structure de données: les tas.

Un tas est un arbre binaire complet tel que tout noeud N contienne une valeur inférieure à toutes les valeurs de ses fils.
Remarque: Les multiples définitions existantes pour " arbre complet " peuvent porter à confusion. Ici, il est important que tous les étages, de la racine jusqu'à l'avant-dernier, soient remplis. De plus, les feuilles de la dernière ligne doivent être "calées à gauche". En revanche, un tas pouvant avoir un nombre quelconque d'éléments, il n'est pas obligatoire que la dernière ligne soit complètement remplie.
Construisez un tas correspondant aux éléments suivants: 47, 2, 9, 6, 13, 7, 41, 12, 56, 5
Soit A un arbre binaire parfait avec n noeuds.
Quelle est sa hauteur?
Si on numérote ses sommets de 1 à n par un parcours en largeur (resp. profondeur), comment connait-on les numéros des fils droits et gauches d'un noeud donné?

Proposez une structure de données pour représenter un tas.
Ecrire des algorithmes pour:
- Insérer un élément dans un tas.
- Trouver et supprimer le plus petit élément d'un tas.
Quelles sont leurs complexités?
Pourquoi n'utilise-t-on pas la recherche dans un tas?
Comment peut-on garantir une bonne complexité de l'ajout et l'extraction du minimum d'un tas ? (indice: modifier la structure de données)

Proposez un algorithme de tri de tableaux utilisant les tas.
Proposez une solution utilisant un unique tableau (i.e. pour les données à trier et la représentation du tas) et implantez là
Quelle est sa complexité?

Implémenter le tri par tas de l'exercice précédent. Faire des tests comparatifs avec qsort().