Sorting algorithms/Heapsort: Difference between revisions

Line 2,910:

acdhijkqw</lang>

=={{header|~~Janet~~}}==

=={{header|etet}}==

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.

<lang janet>~~(defn swap [l a b]~~

(defn swap [l a b]

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

(put l a bval)

Line 2,947:

Line 2,948:

(def val (get heap idx))

(def parent-idx (parent idx))

(if (and (not (nil? parent-idx)) (< val (get heap parent-idx))) ~~(do~~

(when (and (not (nil? parent-idx)) (< val (get heap parent-idx)))

(swap heap parent-idx idx)

(swim parent-idx)

))

)

(check-invariants idx))

Line 2,969:

Line 2,970:

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

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

# NOTE: ~~`true` is used instead of~~ `else` for final branch in cond

# NOTE: The `else` for final branch of `cond` is implicit

~~true~~ (get smaller-children 1)

(get smaller-children 1)

))

(~~if (not~~ (nil? smallest-child)~~) (do~~

(unless (nil? smallest-child)

(swap heap smallest-child idx)

(sink smallest-child)

# Recheck invariants

(check-invariants idx))))

(check-invariants idx)))

(defn insert [val]

Line 2,987:

Line 2,988:

(def largest (get heap ROOT))

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

(if (> (length heap) 1) ~~(do~~

(when (> (length heap) 1)

(put heap ROOT new-root)

(sink ROOT)))

(sink ROOT))

(assert (not (nil? largest)))

largest)