Как эффективно заменить верхний элемент кучи, не восстанавливая инвариант кучи дважды? ⇐ C++

[Anonymous]

tl;dr: Я ищу замену C++ для Python heapq.heapreplace.

Мне нужно обработать максимальную кучу (используемую в качестве приоритетной очереди) таким образом, что я извлекаю верхний элемент, вычитаю неопределенное число и затем снова помещаю этот измененный элемент. Я мог бы сделать это, используя только pop_heap и push_heap, но это требует ненужной работы, поскольку приходится дважды изменять кучу, каждый раз заново устанавливая инвариант кучи:

Код: Выделить всё

std::vector heap;
// ...
std::pop_heap(heap.begin(), heap.end()); // Re-establishes heap invariant.
decrease(heap.back());
std::push_heap(heap.begin(), heap.end()); // Re-establishes heap invariant again.

Эффективный интерфейс может выглядеть примерно так:

Код: Выделить всё

decrease(heap.front()); // Modify in-place.
replace_heap(heap.begin(), heap.end());

Есть ли какая-то хитрость, с помощью которой я могу заставить STL делать то, что я хочу, или мне придется самому писать replace_heap?

Подробнее здесь: https://stackoverflow.com/questions/326 ... g-heap-inv