如何操作boost C++中的优先级队列中的元素

Question

我有一个问题来处理boost C++中的配对优先级队列。我有一个项目数组{0,1,2,3，...}，并且每个项目都有一个优先级值。这些优先级队列构造另一个数组{项目0为key0，项目1为key1，...}。

在算法中，我需要选择几个项目将它们放入优先级队列中。例如，我可以将项目1,2,3选择到队列中，并按其优先级值（键）排序。然后，我需要删除一个特定的项目。例如，我可能想要从项目1,2,3的队列中删除项目2，项目2可能不具有最大/最小优先级值。

下面是我在boost中使用配对队列创建的队列。

#include "stdafx.h" 
#include <iostream> 
#include <boost/heap/pairing_heap.hpp> 
pairing_heap<float> pq; 

pq.push(1); 
pq.push(2.5); 
auto handle = pq.push(3.1); 
pq.erase(handle); // remove an element by handle 
cout << "pq top=" << pq.top() << endl; // a const_reference to the maximum element. 

你可以看到，我只能推的优先级值到队列中，如果我想删除一个项目，我需要知道它的句柄值。但是，我不知道如何处理大量项目的值。希望有人知道如何去做。非常感谢！

Answer 1

您可以使用s_handle_from_iterator

pq.update(Heap::s_handle_from_iterator(pq.begin()), pq.top()*2); 
std::cout << "pq top=" << pq.top() << std::endl; 

打印 “5”。

花了一点挖，但我发现docs陈述操作是常量时间（文档指d_ary_heap源）。

Live On Coliru

#include <boost/heap/pairing_heap.hpp> 
#include <iostream> 

int main() { 
    using Heap = boost::heap::pairing_heap<float>; 
    Heap pq; 

    pq.push(1); 
    pq.push(2.5); 
    auto handle = pq.push(3.1); 
    pq.erase(handle); // remove an element by handle 
    std::cout << "pq top=" << pq.top() << std::endl; // a const_reference to the maximum element. 

    pq.update(Heap::s_handle_from_iterator(pq.begin()), pq.top()*2); 
    std::cout << "pq top=" << pq.top() << std::endl; 
}