tl;dr:我正在寻找 Python 的 heapq.heapreplace
的 C++ 替代品.
我必须以这样一种方式处理最大堆(用作优先级队列):弹出顶部元素,减去一个未指定的数字,然后再次压入修改后的元素。我可以只使用 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, 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>;
关于c++ - 如何在不重新建立堆不变量两次的情况下有效地替换堆顶元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32672474/