Subject: [boost] [review] Heaps: Mergeable Heaps
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-05 09:19:08
I think you should define a MergeableHeap that describes heaps that
can be merged in O(log n) (i.e., binomial, fibonacci, pairing, skew).
Actually, the only heaps that don't satisfy this requirement are
binary heaps, b-heaps and d-ary heaps (they all seem to be linear).
This is similar to the the AdjacencyMatrix in the BGL.
This poses a serious problem, however. The mutable priority queue
wrapper implements merge() as, at best, a linear operation, meaning
that no mutable priority queue could model the MergeableHeap concept.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk