2011-06-02 5 views
1

これを正しく実行しているかどうかを確認するだけです。私はヒープソートのwikiをチェックしましたが、アニメーションではヒープを構築するように見えます。ヒープはノードに数字を挿入し、それをそのまま注文します。有効なヒープを構築する

疑問は、私はいくつかの例には、それを試してみた「ツリーとして{7、12、1、3、22、5、11}。これらの要素と有効なヒープを描く」こと

を依頼しますそして、私は最初にノードをレイアウトしてから、ノードを並べ替えるのではなく、ノードを並べ替えるべきだと思います。私はそれを正しい方法でしていますか?例えば

 7 

    12  1 

3 22 5 11 

ノードに要素を置く順序はここに始まる:スワップ1,7

 7 

    12  1 

3 22 5 11 

スワップ3及び12

 1 

    12  7 

3 22 5 11 

スワップ5,7

 1 

    3  7 

12 22 5 11 

が完了しました。

 1 

    3  5 

12 22 7 11 

実際は正しくありません。与えられた

答えは、私は(3で始まる)最初の左側から再順番にヒープを始めるなら、私は正しい答えを得る

 1 

    7  3 

12 22 5 11 

です。

+0

「ウィキ」とは何ですか?ウィキペディア? –

答えて

3

実際には、ヒープデータ構造は1つのプロパティとして定義され、次のように定義できます。「ヒープTでは、ルート以外のすべてのノードvについて、vに格納されたキーはキーvの親に格納されています。

したがって、要素(7,12,1,3,22,5,11)に基づいてヒープの正しい表現が多数あります。これらの要素を使用して、「挿入と並べ替え」アルゴリズムを適用し、さらに別のバージョンを得ました。

 1 
    3   5 
12 22 7 11 
+0

ありがとうございます。私は複数の答えがあると感じました。ちょうど私は1つしか与えられなかった。 – bigubosu