Les $k$ plus petits éléments

let k_plus_petits arr k =
  let n = Array.length arr in
  let t = cree n in
  for i = 0 to n - 1 do insere t arr.(i) done;
  let rec extraire j = if j = 0 then [] else extrait_min t :: extraire (j - 1) in
  extraire k

On bâtit un tas de tous les éléments, puis on en extrait les k plus petits (les premiers à sortir). Coût $\Theta (n\log n)$ ; on pourrait viser $\Theta (n+k\log n)$ avec une construction de tas en $\Theta (n)$ (exercice 8).