-
Notifications
You must be signed in to change notification settings - Fork 24
/
Heap.cljs
49 lines (45 loc) · 1.24 KB
/
Heap.cljs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
(ns missionary.impl.Heap)
(defn create [^number cap]
(doto (js/Array. (inc cap))
(aset 0 0)))
(defn size [heap]
(aget heap 0))
(defn enqueue [heap i]
(let [j (inc (aget heap 0))]
(aset heap 0 j)
(aset heap j i)
(loop [j j]
(when-not (== 1 j)
(let [p (bit-shift-right j 1)
x (aget heap j)
y (aget heap p)]
(when-not (< y x)
(aset heap p x)
(aset heap j y)
(recur p)))))))
(defn dequeue [heap]
(let [s (aget heap 0)
i (aget heap 1)]
(aset heap 0 (dec s))
(aset heap 1 (aget heap s))
(loop [j 1]
(let [l (bit-shift-left j 1)]
(when (< l s)
(let [x (aget heap j)
y (aget heap l)
r (inc l)]
(if (< r s)
(let [z (aget heap r)]
(if (< y z)
(when (< z x)
(aset heap r x)
(aset heap j z)
(recur r))
(when (< y x)
(aset heap l x)
(aset heap j y)
(recur l))))
(when (< y x)
(aset heap l x)
(aset heap j y)
(recur l))))))) i))