Probleme – Deux usages d'un tas de taille $k$

1. Le tas des $k$ plus grands est un tas MINIMUM. C'est le point contre-intuitif du problème. On maintient un tas de taille au plus $k$ contenant les $k$ plus grands éléments vus jusqu'ici ; sa racine est donc le plus petit des retenus, c'est-à-dire précisément le candidat à l'éviction. Un tas maximum donnerait le plus grand des retenus, dont on n'a rien à faire.

(* Renvoie les k plus grands éléments du flot, dans un ordre quelconque.
   Précondition : k >= 1. Mémoire : O(k), indépendante de n. *)
(* fp_vide, ajoute, extrait, minimum, taille, contenu : la file de priorité
   de l'exercice sur la file de priorité de ce chapitre, un tas MINIMUM
   de couples (priorité, valeur). *)
let k_plus_grands flot k =
  let f = fp_vide () in
  Array.iter (fun x ->
    if taille f < k then ajoute f x x
    else if x > minimum f then begin    (* x bat le plus faible des retenus *)
      ignore (extrait f);
      ajoute f x x
    end) flot;
  contenu f

2. La preuve. Invariant : après avoir lu les $i$ premiers éléments, le tas contient exactement les $\min (i,k)$ plus grands d'entre eux.

• Initialisation : $i=0$, le tas est vide.
• Conservation. Si $i<k$, on ajoute sans rien retirer : les $i+1$ éléments lus sont tous retenus, l'invariant tient. Si $i\ge k$, notons $\mu$ le minimum du tas. Si $x\le \mu$, alors $x$ est inférieur ou égal aux $k$ retenus, donc il n'appartient pas aux $k$ plus grands des $i+1$ : ne rien faire est correct. Si $x>\mu$, alors $x$ appartient aux $k$ plus grands, et $\mu$ — plus petit que $x$ et que les $k-1$ autres retenus — n'y appartient plus : l'échange est exactement la mise à jour requise.
• Terminaison : la boucle fait $n$ tours. À la sortie, le tas contient les $k$ plus grands du flot.

Complexité : $O(n\log k)$ en temps, et surtout $O(k)$ en mémoire, indépendante de $n$. C'est ce dernier point qui compte : le flot peut être un fichier de dix téraoctets, ou n'exister que le temps de passer.

3. La fusion de $k$ listes triées. On place dans un tas minimum le premier élément de chaque liste, accompagné de son origine :

(* Fusionne k listes triées en une seule, triée. N = longueur totale.
   Complexité : O(N log k) en temps, O(k) en mémoire supplémentaire. *)
let fusion listes =
  let k = Array.length listes in
  let f = fp_vide () in
  Array.iteri (fun i l -> if l <> [||] then ajoute f l.(0) (i, 0)) listes;
  let sortie = ref [] in
  while not (est_vide f) do
    let (v, (i, j)) = extrait f in
    sortie := v :: !sortie;
    if j + 1 < Array.length listes.(i) then
      ajoute f listes.(i).(j+1) (i, j+1)     (* on RECHARGE la liste servie *)
  done;
  Array.of_list (List.rev !sortie)

Invariant : le tas contient, pour chaque liste non épuisée, exactement son plus petit élément non encore sorti. Le minimum du tas est donc le minimum global des éléments restants — c'est la correction du procédé. Terminaison : chaque tour sort un élément définitivement ; le variant est le nombre d'éléments non encore sortis. Complexité : $N$ extractions et au plus $N$ insertions dans un tas de taille $\le k$, soit $O(N\log k)$.

4. Les mesures. Mesuré, $n=10^6$ entiers tirés uniformément, $k=10$ :

Un facteur $44$, et les dix mêmes valeurs — vérifié élément par élément. Le rapport théorique est ${\log }_{2}n/{\log }_{2}k=20/3,3\approx 6$ ; le reste vient de ce que le tas ne fait presque rien : après quelques milliers d'éléments, la condition x > minimum f est fausse presque toujours, et le tour se réduit à une comparaison.

Pour la fusion, mesuré : $k=100$ listes de $10000$ éléments, $N=10^6$, fusion en $1,089$ s, résultat vérifié identique au tri complet. Le gain théorique est ${\log }_{2}N/{\log }_{2}k=3$ : la fusion par tas fait trois fois moins de comparaisons qu'un tri de tout le paquet. Et elle ne demande que $O(k)$ de mémoire, ce qui est la vraie raison de son emploi : c'est ainsi qu'on trie un fichier plus grand que la mémoire, en le coupant en morceaux triables, puis en fusionnant.