MkLeftistHeapPQ functorfunctor 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|))\] |