Sorting algorithms/Heapsort: Difference between revisions

acdhijkqw</lang>

 

Translation of [https://gist.github.com/Techcable/c411b3a550e252b1fd681e1fc1734174 this] Python code. Based on R. Sedgwick's Algorithms Section 2.4.

 

Although Janet is a (functional) Lisp, it has support for [https://janet-lang.org/docs/data_structures/arrays.html mutable arrays] and imperative programming.

 

(let [aval (get l a) bval (get l b)]

(put l a bval)

(def val (get heap idx))

(def parent-idx (parent idx))

(swap heap parent-idx idx)

(swim parent-idx)

(check-invariants idx))

(= 1 (length smaller-children)) (get smaller-children 0)

(< (get heap (get smaller-children 0)) (get heap (get smaller-children 1))) (get smaller-children 0)

))

(swap heap smallest-child idx)

(sink smallest-child)

# Recheck invariants

 

(defn insert [val]

(def largest (get heap ROOT))

(def new-root (array/pop heap))

(put heap ROOT new-root)

(assert (not (nil? largest)))

largest)