2

ヒープを使用する必要があるプログラムを作成していますが、ソート方法以外はすべて正常に動作します。明らかに非常に重要です! 私の論理の何が問題なのか、それともばかげた何かが欠けているのかわかりません。しかし、これを見て新鮮な目を向けるといいでしょう。

関数には、もちろんヒープ、ルートの場所である私のベクトルが渡され、述語として STL レスまたはグレーターのいずれかが渡されます。

template<class T,class P>
void upheap(vector<T>& v, int start, P func) {
   T x = v[start];
   while (start > 1 && func(x, v[start/2])) {
      v[start] = v[start/2]; start /= 2;
   }
   v[start] = x;
}

何が間違っているのですか？

4

1 に答える 1

2

ベクトルの最初の要素は v[0] にあります。あなたはそれが v[1] にあると仮定しているようです。これには理由がありますか？

ルートが v[0] にある場合、ノードがインデックス i にある場合、親は int((i-1)/2) にあり ((i-1)>>1 の方が効率的かもしれません)、子はは 2i+1、2i+2 にあります。例えば：

     0
   1   2
 3  4 5  6
78 9A BC DE

一方、ルートが v[1] にある場合、親は int(i/2) (または i>>1) にあり、子は 2i, 2i+1 にあります。例えば：

     1
   2   3
 4  5 6  7
89 AB CD EF

それが問題になる可能性があります。

func(x, v[start/2])が trueかどうかを確認します。func がヒープ条件である場合、それが false かどうかを確認したい場合があります...

ベクトルはすでに v[start] を含めるのに十分な大きさですか? upheap()を使用してアイテムを一度に 1 つずつヒープに追加する場合 ...そしてベクトルのサイズは決して増加しません... (また、v[0] ではなく v[1] から開始します。余分な要素です。)

単純なスキャフォールディング (テスト/デバッグに使用されるが、最終製品の一部ではないコード) ルーチンを作成してヒープを出力し、それをループに追加し、練習データを使用して実行して、どこがうまくいかないかを確認してみましたか?

于 2010-12-03T05:32:25.910 に答える