(********************************************************************)
(*  OCaml code from the book ``Learn Programming with OCaml''       *)
(*  See https://usr.lmf.cnrs.fr/lpo/                                *)
(*                                                                  *)
(*  Sylvain Conchon and Jean-Christophe Filliâtre                   *)
(*  Copyright 2025 Université Paris-Saclay and CNRS                 *)
(*                                                                  *)
(*  Openly licensed via CC BY SA 4.0                                *)
(*  See https://creativecommons.org/licenses/by-sa/4.0/deed.en      *)
(********************************************************************)

(* Program 97 on page 399
   Heapsort on arrays *)

  let rec move_down a k v n =
    let r = 2 * k + 1 in
    if r >= n then
      a.(k) <- v
    else
      let rmax =
        if r+1 < n then if lt a.(r) a.(r+1) then r+1 else r
        else r in
      if le a.(rmax) v then a.(k) <- v
      else begin a.(k) <- a.(rmax); move_down a rmax v n end

  let heapsort a =
    let n = Array.length a in
    for k = n/2 - 1 downto 0 do move_down a k a.(k) n done;
    for k = n-1 downto 1 do
      let v = a.(k) in a.(k) <- a.(0); move_down a 0 v k
    done
  

This document was generated using caml2html