L'arithmétique du tas dans un tableau

1. Le père de $5$ est $\lfloor (5-1)/2\rfloor =2$, qui porte $3$ ; les fils de $1$ sont $2\cdot 1+1=3$ et $2\cdot 1+2=4$, qui portent $9$ et $7$. On vérifie $4\le 9$, $4\le 7$, $3\le 8$ : l'invariant tient.

2. Non. Mesuré : $t[2]=3>t[5]=2$. L'indice $5$ est bien un fils de $2$ ($2\cdot 2+1=5$), et le tas exige $t[2]\le t[5]$. La forme, elle, est correcte — six cases contiguës — mais l'ordre ne l'est pas.

3. C'est la question qui piège, et la réponse dépend du langage.

• En C, mesuré : (0 - 1) / 2 vaut $0$, car la division entière de C99 tronque vers zéro. À $i=0$ on comparerait donc t[0] < t[0], qui est faux, et la boucle s'arrêterait. Le code marcherait — par accident. C'est le pire des cas de figure : une garde qui semble inutile parce que la faute qu'elle prévient est masquée par une convention d'arrondi.
• Dans un langage où la division arrondit vers $-\infty$ — Python, où mesuré (0-1)//2 vaut $-1$ — l'indice $-1$ désigne la dernière case du tableau. On comparerait la racine avec le dernier élément, et l'on pourrait les échanger : le tas serait corrompu, silencieusement.
• Et si l'on écrit le père par décalage, (i - 1) >> 1 — une optimisation courante —, alors mesuré en C : (-1) >> 1 vaut $-1$, car le décalage à droite d'un entier signé est arithmétique. On lirait t[-1], hors du tableau : comportement indéfini.

La leçon : i > 0 n'est pas une précaution, c'est la précondition de « le père de $i$ existe ». On l'écrit parce qu'elle est vraie du problème, jamais parce qu'un test l'a rendue nécessaire.