2

私はこの問題に何時間も悩まされてきましたが、私が見ていない些細な解決策があると感じています。priority_queue を使用して、定義した構造体へのポインターの MinHeap を作成しようとしています。私の問題は、priority_queue テンプレートに一致させるために、この構造体へのポインターの > 演算子をオーバーロードする必要があることです (これは不可能です)。これは、stl 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);
}

現在、この「ヒープ」内の要素は FIFO で返され、並べ替えは行われません。これは、優先順位の比較でポインターがチェックされ、配列内の以前の要素がメモリ内の下位に配置されているためだと思います。どうすればこれを達成できるかについてのヒントを教えてください。

PS。この投稿がスタックオーバーフローの標準に準拠していない場合は申し訳ありません (ルールに従うように最善を尽くしましたが、これが私の最初の投稿です)。二度と同じ過ちを犯さないように、あらゆる批判を歓迎します。

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 に答える