0

ヒープに挿入する場所をどのように追跡しますか: 各サブツリーの高さをチェックする関数を使用すると、アルゴリズムが O(log N) から O(N) に低下すると思います。

各ノードに変数を保持するか、最後の挿入スポットを持つヒープに変数を保持しますか(どのように定義されていますか?)。

4

1 に答える 1

1

ヒープは「ほぼ満杯」の二分木です。したがって、新しい要素を挿入する場所は 1 つしかなく、高さのチェックは必要ありませんが、次の要素を挿入する場所へのポインターが必要です。もちろん、これは O(logn) の高さを確保するのに十分です

于 2011-03-13T11:20:51.443 に答える