有人能解释如何的std ::更大的用于实现priority_queue

Question

std::priority_queue<int, vector<int>, std::greater<int> > pq;

---

我不明白性病的工作::越大优先级队列。 我正在用优先级队列替换minheap。 此代码取自 geeksForGeeks implementation of Prims algorithm using STL

Answer 1

std::priority_queue类型是所谓的容器适配器。它的工作方式是从可用来表示序列的类型开始，然后使用该类型构建优先级队列（特别是，作为二进制堆）。默认情况下，它使用一个向量。

为了做到这一点，优先级队列类型必须知道如何以确定哪些元素比其他元素“更小”的方式来比较元素。默认情况下，它使用小于运算符。

如果你犯了一个标准std::priority_queue<int>，你得到一个优先级队列

• 用来储存std::vector和
• 使用小于运算符比较元素。

在很多情况下，这是你想要的。如果您将元素插入到以这种方式创建的优先级队列中，则会从最大到最小的范围内读取它们。

但在某些情况下，这不是您想要的行为。例如，在Prim算法和Dijkstra算法中，您希望数值以升序顺序而不是降序顺序。要做到这一点，您实际上需要使用大于号运算符而不是小于号运算符来颠倒比较顺序。

要做到这一点，您需要告诉优先队列使用不同的比较方法。不幸的是，优先级队列类型的设计使得如果你想这样做，你还需要指定你想使用的底层容器。我认为这是设计上的一个错误 - 只要能够指定比较器而不是比较器和容器就可以非常好，但是可以玩得开心。语法是

std::priority_queue<int,    // store integers... 
        std::vector<int>, // ... in a vector ... 
        std::greater<int>> // ... comparing using >