TD d'informatique No. 7 : heapsort

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 8 janvier 2001

Bonne année et meilleurs voeux à vous !

1   Les tas

On appelle arbre binaire parfait ou quasi-complet un arbre donc tous les niveaux sont remplis, sauf éventuellement le dernier et, dans ce cas, les feuilles du dernier niveau sont regroupées le plus à gauche possible.

Un arbre binaire parfait peut se représenter facilement dans un tableau. On met la racine en t[1], et les fils du noeud t[k] sont rangés dans t[2k] et t[2k + 1]. On ne se sert pas de la case t[0].

On appelle tas un arbre binaire parfait qui vérifie la propriété suivante : chaque noeud contient une valeur plus petite que celle contenue dans ses éventuels fils.

Les deux opérations de base sur un tas sont l'adjonction d'une valeur et la suppression du minimum. L'adjonction se fait dans la première case vide, puis on compare cette case à son père pour éventuellement intervertir les éléments, puis, s'il y a eu interversion, on compare le père au grand-père...

Pour la suppression, on remplace la racine par le dernier élément du tableau, puis on compare cette valeur au plus petit de ces deux fils pour interversion, puis ce fils à ces deux fils...


Figure 1: À gauche : un exemple d'ajout d'élément dans un tas. À droite : exemple de suppression de la racine.

2   Tri par tas

Le tri par tas est facile à mettre en oeuvre : on ajoute les éléments les uns après les autres dans un tas. Puis on supprime le minimum (que l'on met en fin de tableau) tant que le tas n'est pas vide.

Travail à faire : programmer ce tri !
This document was translated from LATEX by HEVEA.