-
Notifications
You must be signed in to change notification settings - Fork 1
/
core.clj
119 lines (105 loc) · 2.54 KB
/
core.clj
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
(ns clojure-heap.core
(:refer-clojure :exclude [peek]))
;; (def heap (transient []))
(definterface HeapItf
(setArr [arr] "change the heap array")
(getArr [])
(getComp []))
(deftype Heap [^:unsynchronized-mutable arr
^:unsynchronized-mutable comp]
HeapItf
(getArr
[this]
arr)
(getComp
[this]
comp)
(setArr
[this newArr]
(set! arr newArr)))
(defn parent
[i]
(int (Math/floor (/ (- i 1) 2))))
(defn left
[i]
(+ (* 2 i) 1))
(defn right
[i]
(+ (* 2 i) 2))
(defn swap
"swap the value of i and j in heap arr"
[heap i j]
(let [val-i (get heap i)
val-j (get heap j)
heap (assoc! heap i val-j)
heap (assoc! heap j val-i)]
heap))
(defn top-down
[arr comp]
(let [size (count arr)]
(loop [curr 0 arr arr]
(let [l (left curr)
r (right curr)]
(if (>= l size)
arr
(if (>= r size)
;; only left exist
(if (comp (get arr curr) (get arr l))
arr
(recur l (swap arr curr l)))
;; both left and right
(let [curr-val (get arr curr)
l-val (get arr l)
r-val (get arr r)
c-l (comp curr-val l-val)
c-r (comp curr-val r-val)
l-r (comp l-val r-val)]
(if (and c-l c-r)
arr
(if (and c-l (not c-r))
(recur r (swap arr curr r))
(if l-r
(recur l (swap arr l curr))
(recur r (swap arr r curr)))))
)
))))))
(defn bottom-up
[arr comp]
(let [size (count arr)]
(loop [curr (dec size) arr arr]
(let [p (parent curr)]
(if (< p 0)
arr
(if (not (comp (get arr p) (get arr curr)))
(recur p (swap arr p curr))
arr))))))
;; external API
(defn heap
([comp]
(Heap. (transient []) comp))
([comp value]
(Heap. (transient [value]) comp)))
(defn get-size
[heap]
(count (.getArr heap)))
(defn peek
[heap]
(get (.getArr heap) 0))
(defn poll
[heap]
(let [size (get-size heap)
comp (.getComp heap)]
(if (> size 0)
(let [arr (.getArr heap)
arr (swap arr 0 (dec size))
ret (get arr (dec size))
arr (pop! arr)]
(.setArr heap (top-down arr comp))
ret)
nil)))
(defn add
[heap value]
(let [comp (.getComp heap)
arr (.getArr heap)
arr (conj! arr value)]
(.setArr heap (bottom-up arr comp))))