The MkLeftistHeapPQ functor

« 210 Library Documentation

Overview

functor MkLeftistHeapPQ (structure Key : ORDKEY) :> PQ where Key = Key

PQ Cost Specifications

The following costs assume that the work and span of Key.compare is constant.

Work Span
empty $()$
singleton $(k, v)$
size $Q$
findMin $Q$
\[O(1)\] \[O(1)\]
fromList $L$ \[O(|L|)\] \[O(|L|)\]
insert $(Q, (k, v))$
deleteMin $Q$
\[O(\log|Q|)\] \[O(\log|Q|)\]
meld $(A, B)$ \[O(\log(|A| + |B|))\] \[O(\log(|A| + |B|))\]