6 Jun
2011
6 Jun
'11
10:34 a.m.
Is the merge implementation for container adaptors the same? It might be worthwhile implementing it is an algorithm rather than a member function for inefficiently merged heaps.
void merge(Heap& l, Heap& r) {
for(auto& x : r) l.push(x);
}
well, it should be possible to implement it in O(N) instead of O(N log(N)) by using the heap iterators and creating a new heap ...
äh ... actually this is not as straight-forward as i thought, since boost.heap iterators cannot be used to iterate the heap in the order of the nodes. so in fact we need to copy the heap and sequentially extract the top node ... tim