如果我有一个最大堆，如果我需要改变的最大因素，可以归结为一个单一的泡沫倒算法。有没有办法通过C ++标准库要做到这一点，而无需手动编码算法？

If I have a max heap, and if I need to change the max element, it comes down to a single bubble-down algorithm. Is there any way to do this via the C++ standard library, without coding the algorithm by hand?

我的理解应该是相当于pop_heap + push_heap，但是这2泡沫停止运作，而不是只有一个。

I understand it should be equivalent to pop_heap + push_heap, but that's 2 bubble down operations instead of just one.

所以 - 是通过库API公开这个泡沫下降算法

So - is this bubble-down algorithm exposed via the library API?

推荐答案

如果你愿意叫的std :: pop_heap（）在你自己的货柜 v ，那么你可以先 v.push_back（）在容器上弹出堆前的修改元素。然后，收缩 v 。

If you are willing to call std::pop_heap() on your own container v, then you can just first v.push_back() on the container the "modified" element before popping the heap. Then, shrink 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（）被定义为交换的第一个和最后一个元素和气泡下降。但是，要求也指出，输入序列应该是一个有效的堆。如果我们能够限定一个专门比较操作，将允许新推回项目报告本身属于在最后的位置，如果它已经在最后的位置，那么它可以在技术上满足要求。

This "works" because std::pop_heap() is defined to swap the first and last elements and bubble down. However, the requirement is also stated that the input sequence should be a valid heap. If we are able to define a specialized comparison operation that would allow the newly pushed back item to report itself to belong in the last position if it was already in the last position, then it could technically satisfy the requirement.