2

我已经被这个问题困住了好几个小时，但我觉得有一个我没有看到的微不足道的解决方案。我正在尝试使用 priority_queue 创建指向我定义的结构的 MinHeap 指针。我的问题在于必须为指向该结构的指针重载 > 运算符（我知道这是不可能的）以匹配 priority_queue 模板。这是我在决定放弃它并编写自己的堆代码之前使用 stl priority_queue 的最后尝试。

我的代码的相关片段是：（i）部分结构定义：

typedef struct Node Node;
struct Node
{
    int frequency;
    bool operator>( const Node& other ) const{
        return frequency > other.frequency;
    }
};

(ii) 优先队列初始化：

priority_queue<Node*,vector<Node*>,greater<Node*> > q;

以及 (iii) 构造初始堆的 for 循环（假设 int_array 已初始化）：

for (int i = 0; i < SIZEOFINTARRAY; i++)
{
    Node *n = new Node;
    n->frequency = int_array[i];
    q.push(n);
}

目前，这个“堆”中的元素以先进先出的方式返回，并且没有排序发生。我认为这是因为优先级比较检查数组中较早的指针和元素位于内存中的较低位置。请给我有关如何完成此任务的任何提示。

PS。抱歉，如果这篇文章不符合 stackoverflow 标准（我尽力遵守规则，但这是我的第一篇文章）。我欢迎所有的批评，所以我再也不会犯同样的错误了。

4

2 回答 2

3

一种通用的方法是实现一种deref_greater类似于std::greater但首先取消引用输入参数的方法。

template<class T>
struct deref_greater : public std::binary_function<T, T, bool>
{
  bool operator()( const T& _Left, const T& _Right ) const
  {
    return *_Left > *_Right;
  }
};
于 2012-04-19T08:10:30.080 回答
2

您可以为指针实现一个比较器，而不是重载>Node 类上的运算符：Node*

struct NodeGreater
{
    bool operator() ( const Node* lhs, const Node* rhs ) const
    {
        if ( lhs == 0 || rhs == 0 )
        {
            // Perhaps throw an exception here...
        }

        return lhs->frequency > rhs->frequency;
    }
};

priority_queue<Node*,vector<Node*>,NodeGreater> q;
于 2012-04-19T08:05:34.720 回答