Невозможно изменить произвольный элемент кучи во время логарифмической работы без нарушения свойства кучи, просто используя шаблоны функций std::pop_heap()
и std::push_heap()
, которые предоставляет стандартная библиотека.
Однако для этой цели вы можете определить свой собственный шаблон функции, подобный STL, set_heap_element()
:
template<typename RandomIt, typename T, typename Cmp>
void set_heap_element(RandomIt first, RandomIt last, RandomIt pos, T value, Cmp cmp)
{
const auto n = last - first;
*pos = std::move(value); // replace previous value
auto i = pos - first;
using std::swap;
// percolate up
while (i > 0) { // non-root node
auto parent_it = first + (i-1)/2;
if (cmp(*pos, *parent_it))
break; // parent node satisfies the heap-property
swap(*pos, *parent_it); // swap with parent
pos = parent_it;
i = pos - first;
}
// percolate down
while (2*i + 1 < n) { // non-leaf node, since it has a left child
const auto lidx = 2*i + 1, ridx = 2*i + 2;
auto lchild_it = first + lidx;
auto rchild_it = ridx < n? first + ridx: last;
auto it = pos;
if (cmp(*it, *lchild_it))
it = lchild_it;
if (rchild_it != last && cmp(*it, *rchild_it))
it = rchild_it;
if (pos == it)
break; // node satisfies the heap-property
swap(*pos, *it); // swap with child
pos = it;
i = pos - first;
}
}
Затем вы можете предоставить следующую упрощенную перегрузку set_heap_element()
для max heap :
#include <functional> // std::less
template<typename RandomIt, typename T>
void set_heap_element(RandomIt first, RandomIt last, RandomIt pos, T value) {
return set_heap_element(first, last, pos, value, std::less<T>{});
}
Эта перегрузка использует объект std::less<T>
в качестве объекта функции сравнения для исходного шаблона функции.
Пример
В вашем примере max-heap set_heap_element()
можно использовать следующим образом:
std::vector<int> v{1,2,3,5,9,20,3};
std::make_heap(v.begin(), v.end());
// set 4th element to 35 in O(log n)
set_heap_element(v.begin(), v.end(), v.begin() + 3, 35);
Вы можете использовать std::is_heap()
, что занимает линейное время, когда вы хотите проверить* удовлетворяет ли свойство max-heap по-прежнему v
после установки элемента с шаблоном функции set_heap_element()
выше:
assert(std::is_heap(v.begin(), v.end()));
Как насчет min кучи?
можно добиться того жедля min heap путем передачи объекта std::greater<int>
в качестве последнего аргумента вызова функции в std::make_heap()
, set_heap_element()
и std::is_heap()
:
std::vector<int> v{1,2,3,5,9,20,3};
// create a min heap
std::make_heap(v.begin(), v.end(), std::greater<int>{});
// set 4th element to 35 in O(log n)
set_heap_element(v.begin(), v.end(), v.begin() + 3, 35, std::greater<int>{});
// is the min-heap property satisfied?
assert(std::is_heap(v.begin(), v.end(), std::greater<int>{}));