[boost] [review] Heaps: Mergeable Heaps

Subject: [boost] [review] Heaps: Mergeable Heaps
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-05 09:19:08

Tim,

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.

Andrew