如何高效地替换堆顶元素而不需要重新建立堆不变量两次？

Question

tl;dr：我正在寻找 Python 的 C++ 替代品

heapq.heapreplace

。

我必须以这样的方式处理最大堆（用作优先级队列）：弹出顶部元素，减去未指定的数字，然后再次推送该修改的元素。我可以只使用

pop_heap

和

push_heap

来完成此操作，但这会做不必要的工作，因为它必须修改堆两次，每次都重新建立堆不变量：

std::vector<unsigned> 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

？

Answer 1

由于到目前为止还没有答案，所以我已经写了自己的

replace_heap

/

heapreplace

。 C++ 标准不保证

std::push_heap

等人如何维护堆。已实现（理论上它可以是三元而不是二进制堆，甚至可以是完全不同的东西 - 尽管至少 g++ 的 stdlib 有一个普通的二进制堆），所以我还添加了

push_heap

/

heappush

的随附版本。在这里，以防有人觉得有用：

#include <functional> // less
#include <iterator> // iterator_traits
#include <utility> // move

template <typename DifferenceT>
DifferenceT heap_parent(DifferenceT k)
{
    return (k - 1) / 2;
}

template <typename DifferenceT>
DifferenceT heap_left(DifferenceT k)
{
    return 2 * k + 1;
}

template<typename RandomIt, typename Compare = std::less<>>
void heapreplace(RandomIt first, RandomIt last, Compare comp = Compare())
{
    auto const size = last - first;
    if (size <= 1)
        return;
    typename std::iterator_traits<RandomIt>::difference_type k = 0;
    auto e = std::move(first[k]);
    auto const max_k = heap_parent(size - 1);
    while (k <= max_k) {
        auto max_child = heap_left(k);
        if (max_child < size - 1 && comp(first[max_child], first[max_child + 1]))
            ++max_child; // Go to right sibling.
        if (!comp(e, first[max_child]))
            break;
        first[k] = std::move(first[max_child]);
        k = max_child;
    }

    first[k] = std::move(e);
}

template<typename RandomIt, typename Compare = std::less<>>
void heappush(RandomIt first, RandomIt last, Compare comp = Compare())
{
    auto k = last - first - 1; // k = last valid
    auto e = std::move(first[k]);

    while (k > 0 && comp(first[heap_parent(k)], e)) {
        first[k] = std::move(first[heap_parent(k)]);
        k = heap_parent(k);
    }

    first[k] = std::move(e);
}

我仍然对更好的解决方案/需要更少自定义代码的解决方案感兴趣。

编辑：我已将@TemplateRex 和@Deduplicator 的评论中的建议纳入其中。使用不带模板参数的

std::less<>

需要 C++14。如果你被困在 C++11 上，你将不得不使用类似

default_compare<RandomIt>

的东西，定义如下（未经测试）：

template <typename Iter>
using default_compare = std::less<typename std::iterator_traits<Iter>::value_type>;