(def parent (i)
    (trunc (/ i 2)))

(def left (i)
    (* 2 i))

(def right (i)
    (+ 1 (* 2 i)))

(def elm (h i)
    (let ind (- i 1)
        h.ind))

(def setval (h i val)
    (= (h (- i 1)) val)
    h)

(def hswap (h i j)
    (= temp (elm h i))
    (setval h i (elm h j))
    (setval h j temp))

(def t-lgi (h idx (o curr))
    (if (empty idx)
        curr
        (t-lgi h (cdr idx) (if (no curr)
            (car idx)
            (> (elm h (car idx)) (elm h curr))
            (car idx)
            curr))))

(def largesti (h idx (o hsize (len h)))
    (t-lgi h (keep [>= hsize _] idx)))

(def max-heapify (h i (o hsize (len h)))
    (let largest
        (largesti h (list (left i) (right i) i) hsize)
        (when (~is i largest)
            (hswap h i largest)
            (max-heapify h largest hsize)))
      h)

(def build-max-heap (h (o hsize (len h)))
    (each x (rev:range 1 (trunc (/ hsize 2)))
        (max-heapify h x hsize))
    h)

(def heapsort (h)
    (hswap h 1 (len h))
     (each x (rev:range 2 (- (len h) 1))
        (max-heapify h 1 x)
        (hswap h 1 x))
      h)

;test
;(max-heapify '(16 4 10 14 7 9 3 2 8 1) 2)
;(heapsort '(16 14 10 8 7 9 3 2 4 1))