How to use Boost d_ary_heap?

Question

I'm trying to use the Boost d_ary_heap but I cannot figure out how to get the handle for a pushed element. In my case, I will need to update the value in a later iteration, so I need that handle. I was able to do it with the Fibonacci heap but in this case it looks much more complex.

This is what I have so far:

struct compare_cells_d_ary {
inline bool operator()
(const myType * c1 , const myType * c2) const {

    return c1->getValue() > c2->getValue(); // I want a min heap.        
}
};


class MyHeap {

typedef typename boost::heap::d_ary_heap<const myType *, boost::heap::mutable_<true>, boost::heap::arity<2>, boost::heap::compare<compare_cells_d_ary>>::handle_type handle_t;

protected:
    boost::heap::d_ary_heap<const myType *, boost::heap::arity<2>, boost::heap::mutable_<true>, boost::heap::compare<compare_cells_d_ary>> heap_;  
    std::vector<handle_t> handles_; // I store the handles in an specific order.

public:
 /****/
    void push (const myType * c) {
        handles_[c->getIndex()] = heap_.push(c);
    }

 /****/
};

The push function is how I use it in the Fibonacci heap, which returns a handle_type. But in this case I cannot understand what it is supposed to return (http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/d_ary_heap.html#idp52218904-bb)

Any help in how to get the handle when pushing is welcome! Thanks.

Answer 1

Since you declared your heap as mutable, the push operation is supposed to return the handle_t you typedefed as the handle_type:

mpl::if_c< is_mutable, handle_type, void >::type push(value_type const & v);

In the respect of obtaining the handle, your code is fine. To simplify a bit to make it clearer:

void push (const myType * c) {
    handle_t handle = heap_.push(c);
    handles_[c->getIndex()] = handle;
}

As a side-note, you should have a typedef for the heap instead of repeating it in the declarations, and the typename is superfluous (at least in the snippet you posted in the question.)