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 0 à n-1 par un parcours en largeur (resp. profondeur), comment connait-on les numéros des fils droits et gauches d'un noeud donné?
Est-il préférable de coder un tas avec un arbre binaire ou avec un tableau ?

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?

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é?