<div dir="ltr"><div><div>I'm trying to figure out the complexity of the functions in Melissa O'Neill's Priority Queue library, Priority.Q.hs<br><br></div>Below find definitions, and what I think the complexity is. I'd appreciate feedback, especially on the ones I have marked as guesses.<br><br>data PriorityQ k v = Lf<br>                   | Br {-# UNPACK #-} !k v !(PriorityQ k v) !(PriorityQ k v)<br>               deriving (Eq, Ord, Read, Show)<br><br>O(log n) .<br>This is a guess but alternating which side of the sub-tree is being traversed is my hint.<br><br>insert :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v<br>insert wk wv (Br vk vv t1 t2)<br>               | wk <= vk   = Br wk wv (insert vk vv t2) t1<br>               | otherwise  = Br vk vv (insert wk wv t2) t1<br>insert wk wv Lf             = Br wk wv Lf Lf<br><br>I have no idea. Reasoning help here please.<br>siftdown :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v -> PriorityQ k v<br>siftdown wk wv Lf _             = Br wk wv Lf Lf<br>siftdown wk wv (t @ (Br vk vv _ _)) Lf<br>    | wk <= vk                  = Br wk wv t Lf<br>    | otherwise                 = Br vk vv (Br wk wv Lf Lf) Lf<br>siftdown wk wv (t1 @ (Br vk1 vv1 p1 q1)) (t2 @ (Br vk2 vv2 p2 q2))<br>    | wk <= vk1 && wk <= vk2    = Br wk wv t1 t2<br>    | vk1 <= vk2                = Br vk1 vv1 (siftdown wk wv p1 q1) t2<br>    | otherwise                 = Br vk2 vv2 t1 (siftdown wk wv p2 q2)<br><br>Whatever the cost of siftdown is.<br>deleteMinAndInsert :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v<br>deleteMinAndInsert wk wv Lf             = error "Empty PriorityQ"<br>deleteMinAndInsert wk wv (Br _ _ t1 t2) = siftdown wk wv t1 t2<br><br>This looks like O(log N) to me.<br>leftrem :: PriorityQ k v -> (k, v, PriorityQ k v)<br>leftrem (Br vk vv Lf Lf) = (vk, vv, Lf)<br>leftrem (Br vk vv t1 t2) = (wk, wv, Br vk vv t2 t) where<br>    (wk, wv, t) = leftrem t1<br>leftrem _                = error "Empty heap!"<br><br>The cost of siftdown, which is probably more expensive than leftrem.<br><br>deleteMin :: Ord k => PriorityQ k v -> PriorityQ k v<br>deleteMin (Br vk vv Lf _) = Lf<br>deleteMin (Br vk vv t1 t2) = siftdown wk wv t2 t where<br>    (wk,wv,t) = leftrem t1<br>deleteMin _ = error "Empty heap!"<br><br></div>Thanks for the feedback. I'm new to computational analysis and this is the most complicated code I have tried to tackle thus far. I have Okasaki's book, but am having trouble making best use of it.<br><div><br><br><br></div></div>