0

プログラムにヒープを実装しようとしています。ヒープは二分木と同じように思えます。これは、最小ヒープや最大ヒープなどのすべてのヒープに当てはまりますか? 実行されているのは、最大/最小ノードを先頭に配置するツリーのトラバーサルだけなので?

また、1 次元配列の使用は、完全なバイナリ ツリーがある場合にのみ有益であると読みました。完全なバイナリ ツリーがない場合は、別のクラスのフレンド クラスを使用する方が有益でしょうか? 何故ですか?そのような:

template<class T> class BT; // forward declartion -> added at edit

template<class T>
class BTNode{
    friend class BT<T>; // not sure why we need two classes
private:
    T data;
    BTNode<T> *leftChild; // what is the benefit of making a object Node?
    BTNode<T> *rightChild;
};

template<class T>
class BT{
private:
    BTNode<T> *root; // what is the benefit of having this root in another class?
};

前もって感謝します。

4

2 に答える 2

1

標準ライブラリには完全に優れたヒープ実装があります。あなたはそれを見てみるべきです(しかし、それはあなた自身のものを書くこともまた有益な学習練習です. )

バイナリ ヒープはバイナリ ツリーですが、ベクトルとして効率的に格納されます。リンクは暗黙的です。つまり、位置i(0 ベース) のノードの子は、2i+1および2i+2です。(ヒープ内の最大 1 つのノードには 1 つの子しかありません。) つまり、実際にはリンクを格納する必要がないため、小さなデータ オブジェクト (整数など) の場合、少なくとも 3 分の 2 を節約できます。必要なスペース。

ウィキペディアには、バイナリ ヒープ (通常はベクターに格納する種類) に関する優れた記事がありますが、他の種類のヒープに関する記事も多数あります。

于 2012-11-17T03:19:02.823 に答える