如何操作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; 
}