c++ - 可更新优先队列

Question

C++ 标准库中是否有任何内置功能允许我在优先级队列/堆中工作，如数据结构（即，始终可以从列表中弹出最高值，可以定义如何为自定义类确定最高值等。 ) 但允许我更新堆中的键？我正在处理相当简单的数据，确切地说是对，但我需要能够轻松地更新堆中给定键的值，以便我的算法能够正常工作。在 C++ 中实现这一目标的最佳方法是什么？

Answer 1

二进制堆（这是 C++ 标准库中优先级队列的实现方式）不支持任意更新键操作。如果更新不频繁，一个常用的方法是在外部将原始项目标记为无效，并使用新键重新插入该值；当弹出无效值时，将被忽略。

另一种方法是使用不同的 PQ 实现，它支持更新密钥，例如二项式堆。二项式堆具有通过摆动指针而不是移动值来操作的特殊优势。这简化了执行更新键和删除等操作的任务。

Answer 2

我不确定你对Boost的看法是什么，但我总是考虑一种几乎标准的库（一些 boost 功能甚至最终出现在标准库中）。无论如何，如果您对使用 boost 没问题，那么Boost.Heap 会提供一个具有可更新优先级的优先级队列。

像大多数 boost 库一样，它只是头文件，因此没有链接器的麻烦，它不会使您的构建系统变得更加复杂。你可以直接#include使用它。

Answer 3

我没有能力评论你的问题，但这是我的理解。

您提到的对，听起来您需要能够将优先级从对的第一个元素的某些功能更改为第二个元素。

也就是说，您想最初使用下面的 FirstComparator，然后切换到 SecondComparator。

typedef std::pair<X, Y> MyPair;
struct FirstComparator 
{
    bool operator() (const MyPair& left, const MyPair& right) 
    {
        return left.first < right.first;
    }      
}

struct SecondComparator 
{
    bool operator() (const MyPair& left, const MyPair& right) 
    {
        return left.second < right.second;
    }      
}

因为std::priority_queue是一个包含排序标准的模板（正如您提到的问题），您可以创建第二个不同类型的容器。（我写了小于比较，所以我们有一个最小堆。）

您需要将成员转移到其中。

std::priority_queue<MyPair, std::vector<MyPair>, FirstComparator> firstQueue;

// Populate and use firstQueue

// Now create an initially-empty queue sorting according to other criterion,
// and copy elements in.
std::priority_queue<MyPair, std::vector<MyPair>, SecondComparator> secondQueue;

// Use 'push' instead of 'emplace' for pre-C++11 code
while (! firstQueue.empty())
    secondQueue.emplace(firstQueue.pop());  

// Use secondQueue

另一种方法是使用单个std::vector，并std::sort使用不同的排序标准对其进行处理。C++11 允许您创建命名或匿名 lambda 函数，以便即时建立此类排序标准。

由于您的问题具体涉及优先级队列，因此除非您特别感兴趣，否则我不会深入探讨。