The MkSkewBinomialHeapPQ functor

« 210 Library Documentation

Overview

functor MkSkewBinomialHeapPQ(structure OrdKey : ORDKEY) : PQUEUE

Implements PQUEUE.

PQUEUE Cost Specifications

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

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