There's no need to resort when popping an item.

When adding an item, it gets added to the next unused vector element. The sorting range end offset gets updated.

Then it sorts (note you would actually need a custom sort since a PriorityQueue is a pair)

  std::push_heap( vec.begin() + startOffset, vec.begin() + endOffset ) [1]

Adding an item would be something like:

  endOffset++; vec.insert( vec.begin() + endOffset, $value );   [1] 

Or maybe I just used

  endOffset++; vec[endOffset] = $value;  [1]

Popping an item:

  startOffset++;

[1] Im writing this from memory from my attempt many months ago. May have mistakes.. but should communicate the jist