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 QfindMin 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|)) |