Un tas maximum sans réécrire une ligne

Le procédé est correct presque toujours, et son unique défaut est instructif.

Pourquoi il marche. $x\mapsto -x$ renverse l'ordre : $x\le y⟺-x\ge -y$. Le minimum des $-x$ est donc l'opposé du maximum des $x$, et l'invariant de tas minimum sur les opposés est exactement l'invariant de tas maximum sur les valeurs. Aucune ligne du code n'est à changer.

Où il échoue. Sur un type entier signé, l'intervalle n'est pas symétrique : mesuré, INT_MIN vaut $-2147483648$ et INT_MAX vaut $2147483647$. L'opposé de INT_MIN n'est pas représentable : c'est un dépassement signé, donc un comportement indéfini. Mesuré sur cette machine, -INT_MIN rend INT_MIN lui-même ; sur int8_t, -(-128) rend $-128$. Insérer INT_MIN dans le tas négatif y insérerait donc INT_MIN, la plus petite valeur au lieu de la plus grande : elle sortirait en premier au lieu de sortir en dernier.

Trois parades, par ordre de préférence.

• Paramétrer la comparaison plutôt que les valeurs : écrire le tas avec une fonction compare passée à la création. C'est la bonne réponse — elle ne touche pas aux données.
• Interdire INT_MIN par une précondition : assert(x > INT_MIN);. Honnête, mais on a restreint le contrat.
• Renverser en écrivant INT_MAX - x : correct pour $x\ge 0$, et faux dès que $x$ est négatif. À ne pas faire.

C'est le dépassement d'entier silencieux du chapitre chap:langage-c, reparu là où on ne le cherchait plus : une transformation qui préserve l'ordre mathématique ne préserve pas forcément l'ordre machine.