std::priority_queue is a binary heap over a vector, which rules out two things outright: merging two queues cheaply, and changing the priority of an element already inside, because every sift moves elements to different array slots and invalidates anything you were holding. Boost.Heap ships binomial_heap, fibonacci_heap, pairing_heap and skew_heap for precisely those gaps - push returns a handle to a node that never moves, so decrease() reaches the element directly, and merge() folds one heap's node structure into the other instead of popping and re-pushing every element.