File de priorité de couples

type tas_couples = { mutable taille : int; donnees : (int * int) array }

let cree_c capacite = { taille = 0; donnees = Array.make capacite (0, 0) }

let insere_c t x =
  let d = t.donnees in
  d.(t.taille) <- x; t.taille <- t.taille + 1;
  let i = ref (t.taille - 1) in
  while !i > 0 && fst d.((!i - 1) / 2) > fst d.(!i) do
    let p = (!i - 1) / 2 in
    let tmp = d.(!i) in d.(!i) <- d.(p); d.(p) <- tmp; i := p
  done

Tout est identique au tas d'entiers, mais on compare la première composante (fst, la distance) : le couple de plus petite distance remonte à la racine. extrait_min s'adapte de même (comparer par fst). On dispose alors d'une file de priorité « distance, sommet ».