如何在C++标准库中更改堆中的max元素？

Question

如果我有一个最大堆,并且如果我需要更改max元素,那么它归结为单个冒泡算法.有没有办法通过C++标准库来做到这一点,而无需手动编写算法？

我知道它应该等同于pop_heap + push_heap,但是这是2次冒泡操作而不是一次.

那么 - 这个通过库API公开的泡泡算法是什么？

Answer 1

如果您愿意调用std::pop_heap()自己的容器v,那么v.push_back()在弹出堆之前,您可以先在容器上使用"modified"元素.然后,收缩v.

// Precondition is that v is already a heap.
void change_max_element (std::vector<int> &v, int modified_value) {
    v.push_back(modified_value);
    std::pop_heap(v.begin(), v.end());
    v.pop_back();
}

这"有效",因为它std::pop_heap()被定义为交换第一个和最后一个元素并向下冒泡.但是,还要求输入序列应该是有效堆.如果我们能够定义一个专门的比较操作,允许新推回的项目报告自己属于最后一个位置(如果它已经在最后一个位置),那么它在技术上可以满足要求.

Answer 2

您将得到的最接近的是std::make_heap，它可能比简单的弹出/推送慢。

然而，boost 堆有“修复接口”，它允许像你想要的那样进行修改。 http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concepts.mutability