Chercher dans un tas coûte $\Omega (n)$

L'argument tient en une observation : dans un tas minimum, le maximum est nécessairement une feuille. En effet, si un nœud interne portait le maximum, ses fils porteraient des valeurs supérieures ou égales, donc égales au maximum — et à valeurs distinctes, c'est impossible.

Or un arbre complet à $n$ nœuds a $\lceil n/2\rceil$ feuilles : ce sont exactement les indices $\lfloor n/2\rfloor$ à $n-1$ du tableau. Mesuré : $n=7$ donne $4$ feuilles aux indices $3$ à $6$ ; $n=1000$ donne $500$ feuilles aux indices $500$ à $999$.

Conclusion. Chacune de ces $\lceil n/2\rceil$ feuilles peut porter le maximum, et l'invariant de tas ne fournit aucune information pour les départager : il ne compare un nœud qu'à ses descendants, jamais deux nœuds incomparables. Un algorithme qui n'aurait pas examiné toutes les feuilles ne pourrait pas conclure — un adversaire placerait le maximum dans une feuille non examinée. Donc chercher le maximum coûte $\Omega (n)$ comparaisons, et a fortiori chercher une valeur quelconque aussi.

Ce que cela dit de la structure. Le tas répond à « quel est le minimum ? » en $O(1)$ et ne sait rien dire d'autre. Son invariant est plus faible que celui de l'ABR : il n'ordonne pas les frères entre eux. Un invariant plus faible se maintient plus facilement — d'où l'insertion en $O(\log n)$ sans rééquilibrage — et interdit d'autant plus d'usages. C'est le marché à lire avant de choisir sa structure, et le tableau du chapitre le résume.

Le seul élagage possible reste utile en pratique : cherchant $x$ dans un tas minimum, on n'explore pas un sous-arbre dont la racine dépasse $x$. Cela ne change pas la borne — au pire tous les nœuds sont inférieurs à $x$ — mais rend la recherche rapide quand $x$ est petit.