The Boost heap library (at least binomial and fibonacci heaps) requires a default constructor of its comparator in order to call 'pop()' on a heap. I ran into this because I was trying to use a std::binary_negate<> wrapper around another comparator: this has no default constructor. So it's pretty easy to work around; I just have to provide a custom version of binary_negate. However, is this intentional? Should it be fixed? The problem is a little strange; it only surfaces if you call the 'pop()' function of the heap. If you look at the error location, binomial_heap.hpp:831, it is // private constructor, just used in pop() explicit binomial_heap(node_list_type & child_list, size_type size): super_t(value_compare()) To wit, with 1.49 beta 1: #include <boost/heap/binomial_heap.hpp> using namespace boost::heap; struct cmp { # ifdef MAKE_DEFAULT_CONSTRUCTOR cmp() {} # endif cmp(int a) {} bool operator() (int a, int b) const { return a < b; } }; int main() { cmp c(1); binomial_heap<int, compare<cmp> > h(c); h.push(1); # ifdef CALL_POP h.pop(); # endif } Compiling with CALL_POP undefined works. Adding -DCALL_POP then causes a compiler error (the following from GCC 4.3.2, but also witnessed with MSVC10): boost_1_49_0_beta1/boost/heap/binomial_heap.hpp: ... heap.cpp:21: instantiated from here boost_1_49_0_beta1/boost/heap/binomial_heap.hpp:831: error: no matching function for call to ‘cmp::cmp()’ heap.cpp:9: note: candidates are: cmp::cmp(int) heap.cpp:5: note: cmp::cmp(const cmp&) Adding -DMAKE_DEFAULT_CONSTRUCTOR works again.