从STL优先队列创建最小堆

Question

我正在使用stl优先级队列创建小根堆。这是我使用的类。

class Plane
{
  private :
    int id ;
    int fuel ;
 public:
    Plane():id(0), fuel(0){}
    Plane(const int _id, const int _fuel):id(_id), fuel(_fuel) {}

    bool operator > (const Plane &obj)
    {
        return ( this->fuel > obj.fuel ? true : false ) ;
    }

在主函数中，我这样实例化一个对象。

 priority_queue<Plane*, vector<Plane*>, Plane> pq1 ;
 pq1.push(new Plane(0, 0)) ;

我收到一个来自xutility的错误，但我无法理解。

d:\microsoft visual studio 10.0\vc\include\xutility(674): error C2064: term does not evaluate to a function taking 2 arguments

希望能得到解决方案的帮助。

- Sasha

Answer 1

如果您不使用指针（因为它们对于简单结构而言过于复杂），那么您可以使用来自头文件functional的std::greater：

std::priority_queue<Plane, std::vector<Plane>, std::greater<Plane> > pq1;
pq1.push(Plane(0, 0));

目前，您正在将Plane作为比较类型进行传递。这样做是行不通的，因为比较类型必须是函数对象的一种类型，即它必须具有执行比较的operator()。 而Plane没有这样的成员（为此添加该成员只会导致问题）。

std::greater具有适当的方法，是基于您的operator>实现的。但是，它不能用于指针，因为那样它将使用指针比较（基于内存地址）。

顺便说一下，注意您的比较函数可以更简洁地表达为

bool operator>(const Plane &other)
{
    return fuel > other.fuel;
}

- Fred Foo

---

好的，但是如果想要我点赞，这个答案需要解释一下为什么元素类型不适合作为比较器类型，以及因此为什么OP的原始代码无法编译。 :-) - Lightness Races in Orbit

它可以正常工作，但我无法理解原因，就像@Lightness Races in Orbit所提到的那样。 - Sasha

@larsmans 它怎么知道它必须根据我的燃料来排序？ - Sasha

std::greater 会调用你的 operator>，它知道该怎么做。 - Lightness Races in Orbit

@Sasha：那么另一个答案就是你需要的。你不能在指针上重载operator>，因为它已经被定义过了。 - Fred Foo

Answer 2

第三个模板参数必须是一个二元函数，接受两个Plane*类型的参数。你的Plane类没有提供这样的函数。

你需要使用如下形式的函数：

struct CompPlanePtrs
{
  bool operator()(const Plane* lhs, const Plane* rhs) const {
    return lhs->fuel > rhs->fuel ;
  }
};

- juanchopanza

---

我可以用运算符>来做这个吗？让它成为一个友元函数？ 使用operator()也不行。 - Sasha

@ Sasha，问题在于你需要比较指向“Planes”的指针，而不是“Planes”本身。你不能为指针重载operator>。 - juanchopanza