Probleme – Une pile qui connaît son minimum

1. La solution évidente et son défaut. Parcourir les $n$ éléments coûte $\Theta (n)$ par appel de minimum. Retenir le minimum dans un champ ne suffit pas : empiler sait le mettre à jour en $\Theta (1)$, mais depiler ne le sait pas — si l'on retire précisément le minimum, il faut retrouver le suivant, et l'information a disparu. C'est le défaut à nommer : une valeur agrégée se maintient facilement à l'ajout et pas au retrait.

2. La réalisation. On empile, à côté de chaque valeur, le minimum de la pile à ce moment-là.

/* Pile d'entiers connaissant son minimum.
   INVARIANT : pour tout i < n, mn[i] = min(v[0], ..., v[i]). */
typedef struct { int* v; int* mn; int n; int cap; } pilemin;

void empiler(pilemin* p, int x) {
    assert(p->n < p->cap);
    p->v[p->n] = x;
    p->mn[p->n] = (p->n == 0 || x < p->mn[p->n - 1]) ? x : p->mn[p->n - 1];
    p->n = p->n + 1;
}
int depiler(pilemin* p) { assert(p->n > 0); p->n = p->n - 1; return p->v[p->n]; }
int minimum(const pilemin* p) { assert(p->n > 0); return p->mn[p->n - 1]; }

Les trois opérations font un nombre borné d'accès : $\Theta (1)$ chacune. Mesuré, sur la suite $5,3,7,3,8,1$ :

empile 5 -> min 5    empile 3 -> min 3    empile 7 -> min 3
empile 3 -> min 3    empile 8 -> min 3    empile 1 -> min 1
depile 1 -> min 3    depile 8 -> min 3    depile 3 -> min 3
depile 7 -> min 3    depile 3 -> min 5

3. La preuve, et le piège des valeurs répétées.

L'invariant est écrit dans le code : $\text{mn}[i]$ est le minimum de $v[\mathrm{0..}i]$. Il tient pour $i=0$ ($\text{mn}[0]=v[0]$), et il se conserve puisque $\min (v[\mathrm{0..}i])=\min (v[i],\min (v[\mathrm{0..}i-1]))$. La valeur rendue par minimum est $\text{mn}[n-1]$, c'est-à-dire le minimum de toute la pile.

Le dépilage ne détruit rien, et c'est ce qui rend la solution correcte : les cases au-delà de $n$ ne sont plus lues, et $\text{mn}[n-1]$ redevient automatiquement le minimum de ce qui reste. C'est parce qu'on a mémorisé une valeur par niveau, et non une valeur globale, que le retrait est gratuit.

Le piège des répétitions apparaît dans la variante à deux piles, souvent proposée pour économiser la mémoire : on tient une pile auxiliaire des minima, on n'y empile $x$ que si $x<\text{sommet}$, et l'on dépile le sommet auxiliaire quand la valeur retirée lui est égale. Elle est fausse, et la suite $3,3$ suffit à le montrer. Mesuré :

suite 3, 3
  apres les deux empilages : min (version <) = 3       min (version <=) = 3
  apres UN depilage        : min (version <) : PILE DES MINIMA VIDE
                             min (version <=) = 3      (correct : il reste un 3)

Avec l'inégalité stricte, le second $3$ n'a pas été empilé dans la pile auxiliaire ; le dépilage du second, qui vaut $3$, vide pourtant cette pile — et la structure ne sait plus que le $3$ restant est son minimum. La correction est d'employer l'inégalité large $x\le \text{sommet}$ à l'empilage, ce qui garde une copie du minimum par exemplaire.

La réalisation par tableau parallèle donnée plus haut n'a pas ce problème du tout, puisqu'elle range une valeur par niveau sans jamais se demander si c'est la même. C'est un argument sérieux en sa faveur : elle est plus grosse et plus simple à prouver, et sur une structure qu'on écrit une fois pour l'employer partout, la simplicité de preuve vaut la mémoire.

4. Et pour une file ? Oui, et l'on a déjà tout ce qu'il faut. Une file se réalise avec deux piles (exercice de ce chapitre) ; si chacune des deux est une pile-qui-connaît-son-minimum, le minimum de la file est le plus petit des deux minima, en $\Theta (1)$. Les opérations restent en $O(1)$ amorti par le même argument de transfert unique.

Ce que le problème illustre. Enrichir une structure abstraite, c'est ajouter une donnée redondante et un invariant qui la lie à l'état. Le coût est en mémoire — ici un entier par élément — et le bénéfice est un changement d'ordre sur une opération. Le tas du chapitre chap:tas est la version générale de la même idée : maintenir en permanence de quoi répondre en $O(\log n)$ à une question qui coûterait $\Theta (n)$.