gistfile1.clj

(ns clojure-playground.core
  (:require [clojure.contrib.math :as math]))

(defmacro not== [& body]
  `(not (== ~@body)))

(defn parent [i] (math/floor (/ (- i 1) 2)))

(defn left-child [i] (+ (* 2 i) 1))

(defn right-child [i] (+ (* 2 i) 2))

(defn swap [v i j] (let [val-i (v i) val-j (v j)]
                     (assoc v i val-j j val-i)))

(defn get-largest [v i left right]
  (let [heap-last-index (dec (count v))
        largest (if (and (<= left heap-last-index) (> (v left) (v i))) left i)]
    (if (and (<= right heap-last-index)
             (> (v right) (v largest)))
      right largest)))

(defn max-heapify [v i]
  "Ensure that the max-heap invariant holds at i."
  (let [left (left-child i) 
        right (right-child i)
        largest (get-largest v i left right)]
    (if (not== largest i)
      (max-heapify (swap v i largest) largest)
      v)))

(defn heap-sort [v]
  "Loop over all nodes that are not leaves and up, ensuring that the max-heap
   invariant holds at this position."
  (loop [v v i (parent (dec (count v)))]
    (if (== i -1)
      v
      (recur (max-heapify v i) (dec i)))))

(defn main-heap-sort []
  (let [rands (vec (take 4 (repeatedly rand)))
        _ (println rands)
        sorted (heap-sort rands)]
    (println sorted)))

(main-heap-sort)