Une file de priorité sur des couples, et la diminution de clé

Le tas porte des couples. On range dans le tas des couples (priorite, valeur) et l'on compare sur la seule première composante :

(* File de priorité minimum sur des couples (priorité, valeur).
   INVARIANT : pour tout i > 0, fst t.(i) >= fst t.((i-1)/2), et n <= |t|. *)
type 'a fp = { mutable t : (int * 'a) array; mutable n : int }

Les fonctions ajoute et extrait sont celles du cours, où l'on remplace t.(i) < t.(j) par fst t.(i) < fst t.(j).

La diminution de clé, par insertion paresseuse. Plutôt que de chercher l'élément — ce qui coûterait $\Omega (n)$, exercice précédent — on réinsère le même élément avec sa nouvelle priorité, plus petite, sans retirer l'ancienne entrée. Au moment de l'extraction, on ignore tout élément déjà servi :

let vus = Hashtbl.create 97 in
while not (est_vide f) do
  let (p, x) = extrait f in
  if not (Hashtbl.mem vus x) then begin
    Hashtbl.add vus x ();
    traiter x p                    (* la PREMIÈRE sortie est la bonne *)
  end
  (* sinon : entrée périmée, on la jette silencieusement *)
done

Mesuré sur cinq personnes de priorités $7,2,9,4,2$, puis Zoé réinsérée à la priorité $1$ : l'ordre de sortie est Zoé(1) ; Cyril(2) ; Ali(2) ; Béa(4) ; Dupont(7) ; [Zoé(9) ignorée]. La bonne priorité sort la première, la périmée est jetée à la fin.

Correction. Comme la nouvelle priorité est inférieure à l'ancienne, l'entrée neuve sort avant la périmée : la première sortie d'un élément porte donc bien sa priorité minimale. Ce raisonnement s'effondre si l'on augmente une clé — le procédé ne vaut que pour la diminution, ce qui est exactement ce dont Dijkstra a besoin.

Le coût. La file peut contenir jusqu'à $m$ entrées au lieu de $n$, donc $O(\log m)$ par opération au lieu de $O(\log n)$ — mais $\log m\le 2\log n$ pour un graphe simple, la complexité de Dijkstra reste $O((n+m)\log n)$. On échange de la mémoire contre l'abandon d'une opération que la structure ne sait pas offrir. C'est le bon réflexe : plutôt que de forcer une structure à faire ce qu'elle ne sait pas, on reformule le problème pour n'employer que ce qu'elle sait faire.

Un détail que la mesure révèle : Cyril(2) sort avant Ali(2) alors qu'Ali a été inséré le premier. Un tas n'est pas stable — à priorités égales, l'ordre de sortie est arbitraire. Si la stabilité importe, on range le couple $(p,\text{numeˊro d’arriveˊe})$ comme priorité.