読者です 読者をやめる 読者になる 読者になる

Boost.Heap 値の更新

C++

Boost.Heapの特徴の一つとして、「値を変更できる」というのがあります。
キューに一旦登録した値へのハンドルを持っておき、それを使ってupdate()/update_lazy()による更新を行うことができます。

#include <iostream>
#include <algorithm>
#include <boost/heap/fibonacci_heap.hpp>

int main ()
{
    boost::heap::fibonacci_heap<int> que;

    decltype(que)::handle_type h1 = que.push(3);
    decltype(que)::handle_type h2 = que.push(1);
    que.push(4);

    que.update(h1, 6);      // すぐに更新
    que.update_lazy(h2, 8); // 遅延更新 : イテレータで値を参照しようとしたときに更新される

    std::for_each(que.ordered_begin(), que.ordered_end(), [](int x) {
        std::cout << x << std::endl;
    });
}
6
8
4

Boost.Heap documentation - Concepts & Interface : Mutability