c – 如何在不重新建立堆不变量的情况下有效地替换堆的顶层元素？

概述tl; dr：我正在寻找 Python的 heapq.heapreplace的C替代品. 我必须以这样的方式处理max-heap(用作优先级队列),我d出顶部元素,减去未指定的数字,然后再次推送该修改后的元素.我可以使用pop_heap和push_heap来完成这项工作,但这样做不必要,因为它必须修改堆两次,每次重新建立堆不变量： std::vector<unsigned> heap;// .. tl; dr：我正在寻找 Python的 heapq.heapreplace的C替代品.

我必须以这样的方式处理max-heap(用作优先级队列),我d出顶部元素,减去未指定的数字,然后再次推送该修改后的元素.我可以使用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> // movetemplate <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>;

总结

以上是内存溢出为你收集整理的c – 如何在不重新建立堆不变量的情况下有效地替换堆的顶层元素？全部内容，希望文章能够帮你解决c – 如何在不重新建立堆不变量的情况下有效地替换堆的顶层元素？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。