私はヒープを使用する必要があるプログラムを作成しています。私の仕分け方法以外にもすべてがうまく動作します。私は自分の論理に何が間違っているのか、何か愚かなことを逃しているのかどうかはわかりません。しかし、これを見る目の新鮮なセットがいいだろう。C++切り分けヒープ
関数は、ヒープ、ルートの場所、そして述語としての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;
}
何が悪いと思いますか？
ベクトルの最初の要素はv [0]です。あなたはそれがv [1]にあると仮定しているようです。これには理由がありますか？
インデックスがiのノードの場合、ルートがv [0]にある場合、親は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 [スタート/ 2]）が真であるかどうかを確認します。 funcがヒープ条件である場合は、それが偽であるかどうかを確認したい場合があります。
ベクトルは既にv [start]を含む大きさですか？ upheap（）が一度に1つずつヒープに項目を追加するために使用されている場合...そしてベクトルのサイズは決して増加しません...（また、v [1]ではなくv [0]から開始しています。これは余分な要素です。）ヒープを印刷してループに追加して実行する簡単な足場（テスト/デバッグに使用されるコードで最終的な製品の一部ではありません）を作成しようとしましたか？物事がどこから消え去るかを知るための練習データ？
ヒープのルートを通過しているとしますか？あなたは癒しを必要とする要素のインデックスを渡すべきではありませんか？ –
申し訳ありませんええ、私はそのインデックス値を意味するものですね。 – rajh2504
おそらく、不変条件、事前条件、事後条件を書いて、おそらく問題が発生するでしょう。たとえば、入力時に 'HEAP（i = 0 .. start-1）'という条件がtrueになっていますか？そして、目的は、終了時に 'HEAP（i = 0..start）'という条件をtrueにすることです。 –