Vérifier la propriété de tas

let est_un_tas d n =
  let ok = ref true in
  for i = 1 to n - 1 do
    if d.((i - 1) / 2) > d.(i) then ok := false   (* parent > enfant : violé *)
  done;
  !ok

Il suffit de vérifier, pour chaque nœud i (sauf la racine), qu'il n'est pas plus petit que son parent. Parcourir une seule fois les indices 1..n-1 suffit : chaque relation parent-enfant est ainsi testée. Coût $\Theta (n)$.