Currently all the existing solutions are telling you that your tests are poor and this kata is probably a bad idea to begin with.

Also:

• setElement is not tested. In fact it's not even part of the priority_queue
• Operation complexity is not tested at all, so even doing it with O(n^3) or worse can pass the test easily

Until you actually add specifications about the expected behaviours of the member functions of this PriorityQueue, we're all left to guesswork to solve the kata, which means your kata is incomplete and shouldn't even be published.

I am not good in C++ so I can't do this.. Maybe add ruby , python or javascript ?