Acontece que eu bati em uma parede quando não li a documentação cuidadosamente para usar push heap e pop heap da biblioteca C ++ STL.
Em poucas palavras
vector<T> myHeap;
myHeap.push_back(T);
push_heap(myHeap.begin(), myHeap.end(), CompareFunction);
// It doesn't actually pop the heap, but put the element at the end
// of the array
push_heap(myHeap.begin(), myHeap.end(), CompareFunction);
// It actually pops the element
myHeap.pop_back();