tl; dr：我正在寻找
Python的
heapq.heapreplace的C替代品.
我必须以这样的方式处理max-heap(用作优先级队列),我弹出顶部元素,减去未指定的数字,然后再次推送该修改后的元素.我可以使用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？
解决方法
由于到目前为止还没有答案,我已经编写了自己的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,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>;
