如何有序遍历Boost.Heap优先级队列并更新给定的元素？ [英] How to orderly traverse a Boost.Heap Priority Queue and update a given element?

问题描述

我在寻找一个可以维护其元素排序的好数据结构。目前，我尝试 Boost.Heap 。 p>

我经常需要有序遍历数据结构，当基于某些属性到达一个元素时，更新它的优先级。 Boost.Heap优先级队列提供有序和非有序迭代器。元素更新通过节点句柄发生，句柄可以从普通的非有序迭代器获得，但不能直接从有序的迭代器获得，如下例所示：

  #include< iostream> 
 #include< algorithm> 
 #include< boost / heap / fibonacci_heap.hpp> 
 
使用命名空间boost :: heap; 
 
 int main（）
 {
 fibonacci_heap< int> fib_heap; 
 
 fib_heap.push（1）; 
 fib_heap.push（2）; 
 fib_heap.push（3）; 
 
 for（auto i = fib_heap.ordered_begin（）; i！= fib_heap.ordered_end（）; ++ i）
 {
 //这里没有可行的转换
 auto h = fibonacci_heap< int> :: s_handle_from_iterator（i）; 
 
 if（* h == 2）// dumb test 
 {
 fib_heap.increase（h，* h + 2）; 
 break; 
} 
} 
 
 std :: for_each（fib_heap.ordered_begin（），fib_heap.ordered_end（），
 []（const int& e）
 {
 std :: cout<< e<< std :: endl; 
}）; 
} 
  

如何在遍历中有序遍历队列和更新元素？ / p>

请注意，我在更新后离开遍历。

（欢迎使用替代库的建议） / p>

解决方案

如果我找不到更好的替代方案，我需要保存句柄在每个相应的元素以后使用1y代码）：

  #include< iostream> 
 #include< algorithm> 
 #include< boost / heap / fibonacci_heap.hpp> 
 
使用命名空间boost :: heap; 
 
 template< typename T> 
 struct heap_data 
 {
 typedef typename fibonacci_heap< heap_data> :: handle_type handle_t; 
 handle_t handle; 
 T data; 
 
 heap_data（const T& data_）：data（data_）{} 
 
 bool operator<（heap_data const& rhs）const 
 {
返回数据rhs.data; 
} 
}; 
 
 void setup_handle（fibonacci_heap< heap_data< int>> :: handle_type&& handle）
 {
（* handle）.handle = handle; 
} 
 
 int main（）
 {
 fibonacci_heap< heap_data< int>堆; 
 
 setup_handle（heap.emplace（1））; 
 setup_handle（heap.emplace（2））; 
 setup_handle（heap.emplace（3））; 
 
 std :: find_if（heap.ordered_begin（），heap.ordered_end（），
 [& heap]（const heap_data< int>& e）
 {
 if（e.data == 2）
 {
 const_cast< heap_data< int>>（e）.data + = 2; 
 heap.increase句柄）; 
 return true; 
} 
 return false; 
}）; 
 
 std :: for_each（heap.ordered_begin（），heap.ordered_end（），
 []（const heap_data< int>& e）
 {
 std :: cout<< e.data<< std :: endl; 
}）; 
} 
  

I'm looking for a good data structure that can maintain its elements sorted. Currently I'm trying Boost.Heap.

I frequently need to orderly traverse the data structure and when reaching an element based on some property, update its priority. Boost.Heap priority queues provide ordered and non-ordered iterators. Element updates occurs through a node handle, a handle can be obtained from a ordinary non-ordered iterator, but not directly from a ordered one as in the following example:

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

using namespace boost::heap;

int main()
{
    fibonacci_heap<int> fib_heap;

    fib_heap.push(1);
    fib_heap.push(2);
    fib_heap.push(3);

    for(auto i = fib_heap.ordered_begin(); i != fib_heap.ordered_end(); ++i)
    {
        // no viable conversion here
        auto h = fibonacci_heap<int>::s_handle_from_iterator(i);

        if(*h == 2) // dumb test
        {
            fib_heap.increase(h, *h + 2);
            break;
        }
    }

    std::for_each(fib_heap.ordered_begin(), fib_heap.ordered_end(),
    [](const int &e)
    {
        std::cout << e << std::endl;
    });
}

How can I orderly traverse the queue and update an element in the traversal?

Note that I leave traversal after the update.

(Suggestions of alternative libraries for such purpose are welcome)

解决方案

If I find no better alternative, I'll need to save the handle inside each corresponding element for later usage (c++1y code):

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

using namespace boost::heap;

template<typename T>
struct heap_data
{
    typedef typename fibonacci_heap<heap_data>::handle_type handle_t;
    handle_t handle;
    T data;

    heap_data(const T &data_) : data(data_) {}

    bool operator<(heap_data const & rhs) const
    {
        return data < rhs.data;
    }
};

void setup_handle(fibonacci_heap<heap_data<int>>::handle_type &&handle)
{
    (*handle).handle = handle;
}

int main()
{
    fibonacci_heap<heap_data<int>> heap;

    setup_handle(heap.emplace(1));
    setup_handle(heap.emplace(2));
    setup_handle(heap.emplace(3));

    std::find_if(heap.ordered_begin(), heap.ordered_end(),
    [&heap](const heap_data<int> &e)
    {
        if(e.data == 2)
        {
            const_cast<heap_data<int> &>(e).data += 2;
            heap.increase(e.handle);
            return true;
        }
        return false;
    });

    std::for_each(heap.ordered_begin(), heap.ordered_end(),
    [](const heap_data<int> &e)
    {
        std::cout << e.data << std::endl;
    });
}

这篇关于如何有序遍历Boost.Heap优先级队列并更新给定的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！