c++ - 如何创建节点结构类型的 Min stl priority_queue

Question

struct node
{
node *right;
node *left;
int data;   
};

这是我的结构节点。现在我正在使用 stl 优先级队列来提取最小值，即像这样从优先级队列中提取最小值

    std::priority_queue<node*, std::vector<node*>, std::greater<node*> > mypq;

但是我没有得到最小值并且用谷歌搜索，我发现（更大），它用于整数，我得到了另一个答案，我像这样实现

 struct compare  
 {  
 bool operator()(const node*& l, const node*& r)  
  {  
   return l > r;  
   }  
 };

而我是这样使用的

  std::priority_queue<node*, std::vector<node*>,compare > mypq;

但它显示错误我很沮丧，请任何人帮助我

score 3 · Accepted Answer

比较函数应该接受两个参数，它们是优先级队列中元素的类型。你的元素的类型是node*，所以你的函数应该定义为bool operator()(node* l, node* r)。现在，您可以在考虑到这一点的情况下编写比较函数：

struct compare  
{  
  bool operator()(node* l, node* r)  
  {  
    return l->data > r->data;  
  }  
};

score 2 · Accepted Answer

struct compare  
 {  
 bool operator()(const node*& l, const node*& r)  
  {  
   return l->data > r->data;  
   }  
 };

score 1 · Accepted Answer

假设您想使用data结构的字段进行比较，这种类型的仿函数应该可以工作：

struct compare  
{  
  bool operator()(const node* l, const node* r)  const
  {  
    return l->data > r->data;  
  }  
};

这bool operator()是const因为调用它不应该改变它的状态。C++ 标准不要求它是 const 方法，但某些实现可能需要它，从而导致编译错误。

3 回答 3