The MkSkewBinomialHeapPQ functor

« 210 Library Documentation

Overview

functor MkSkewBinomialHeapPQ (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$
insert $(Q, (k, v))$
\[O(1)\] \[O(1)\]
fromList $L$ \[O(|L|)\] \[O(|L|)\]
deleteMin $Q$ \[O(\log|Q|)\] \[O(\log|Q|)\]
meld $(A, B)$ \[O(\log(|A| + |B|))\] \[O(\log(|A| + |B|))\]