Sure, but I think the issue is that 'reasonable scales' are growing larger and larger due to the improvement in constant factors associated with use of vectors.

Sure, but I think the issue is that 'reasonable scales' are growing larger and larger due to the improvement in constant factors associated with use of vectors. Especially if you already know the size you need to allocate it can be quicker to dump the data into the vector and then sort it than to branch hither-and-yon while maintaining an ordering invariant during push_back(). Of course there's probably some kind of cache-aware binary heap that gives the best of both worlds (algorithmic complexity and constant factor improvements), but vector<> already works now without needing fancy things like Judy arrays. The real answer (as ever) is probably to profile to be sure.