Est-ce un tas ?

$T[0:n]$ est un tas si et seulement si chaque case $i\ge 1$ est inférieure ou égale à son père $(i-1)/2$.

static boolean estTas(int[] T, int n) {
    // I(i) : pour tout j dans [1:i], T[(j-1)/2] >= T[j]
    for (int i = 1; i < n; i++) if (T[(i - 1) / 2] < T[i]) return false;
    return true;
}

14.9 : true false true

$[9,7,8,3,5,6,1]$ est un tas. $[9,7,8,3,8,6,1]$ n'en est pas un : la case $4$ (valeur $8$) a pour père la case $1$ (valeur $7<8$). Le troisième test est le tas construit dans l'exercice 14.1. Un tableau trié par ordre décroissant est toujours un tas, puisque le père $(i-1)/2$ précède $i$. La réciproque est fausse. La fonction fait au plus $n-1$ comparaisons : $\Theta (n)$.

nom : T
valeurs : 9 7 8 3 8 6 1
colorier : 1 4
fleches : 1->4:7<8
legende : la case 4 dépasse son père, la case 1 : ce n'est pas un tas