Here's a trick and possibly funky algorithm, for some definition of funky:
(Lots of stuff left out, just to give the idea):
template<typename T> class pseudoHeap {
private:
using iterator = typename vector<T>::iterator;
iterator max_node;
vector<T> heap;
bool heapified;
void find_max() {
max_node = std::max_element(heap.begin(), heap.end());
}
public:
void update(iterator node, T new_val) {
if (node == max_node) {
if (new_val < *max_node) {
heapified = false;
*max_node = new_val;
find_max();
} else {
*max_node = new_val;
}
} else {
if (new_val > *max_node) max_node = new_val;
*node = new_val;
heapified = false;
}
T& front() { return &*max_node; }
void pop_front() {
if (!heapified) {
std::iter_swap(vector.end() - 1, max_node);
std::make_heap(vector.begin(), vector.end() - 1);
heapified = true;
} else {
std::pop_heap(vector.begin(), vector.end());
}
}
};
Keeping a heap is expensive. If you do n updates before you start popping the heap, you've done the same amount of work as just sorting the vector when you need it to be sorted (O(n log n)). If it's useful to know what the maximum value is all the time, then there is some reason to keep a heap, but if the maximum value is no more likely to be modified than any other value, then you can keep the maximum value always handy at amortized cost O(1) (that is, 1/n times it costs O(n) and the rest of the time it's O(1). That's what the above code does, but it might be even better to be lazy about computing the max as well, making front() amortized O(1) instead of constant O(1). Depends on your requirements.
As yet another alternative, if the modifications normally don't cause the values to move very far, just do a simple "find the new home and rotate the subvector" loop, which although it's O(n) instead of O(log n), is still faster on short moves because the constant is smaller.
In other words, don't use priority heaps unless you're constantly required to find the top k values. When there are lots of modifications between reads, there is usually a better approach.