- ベストアンサー
ヒープって・・・？
ヒープソートなんかで使いますが、ヒープそのものはどうやって作るんですか？ ルートに最大の値が来て・・・ってのは解ってるのですが、そんな並べ替えをロジックでやってたら、ヒープを作る前にソートできてますよね？^^; ヒープってやつに値を入れたら勝手に並ぶんですか？
- peugeot307
- お礼率86% (57/66)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数3
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
こちらを参考にどうぞ。
関連するQ&A
- 【ヒープの作り方】
データ構造やアルゴリズムについての質問です。 「ヒープ」を用いてソートができたりすること、 ヒープへ挿入や、ヒープからの削除は分かるのですが、 そもそもヒープの作り方が分かりません。 ≪作り方≫ ある要素の集合が与えられたとき、 １つ目の値をルートにもってくる ２つ目の値をルートと比較し、子≦ルートとなるように追加 ３つ目の値をルートと比較し、子≦ルートとなるように追加 ４つ目の値をルートの左の子と比較し、子≦ルートの左の子、かつルートとも比較 ..... という風に要素の集合から要素がなくなるまで続けるので正しいでしょうか？ それとも初めに与えられた要素の集合を ひとまず要素数分の２分木構造に割り当て、 ヒープが成り立つように、あとから値の交換を 行うのでしょうか？ いま、要素の集団は配列のように順番が決まっているとして 考えています。 ≪取り出しと削除≫ 値の「取り出し」と「削除」は別物。という認識は正しいでしょうか？ (1)取り出し...末端の最も右の葉をルートにコピーし、ヒープを再構成。 ⇒ルートの値を取り出す。 (2)削除...削除したい値を削除し、その子孫を繰り上げる。 詳しい方がおられましたら、ご指摘、アドバイス等 どうぞよろしくお願い致します。
- ベストアンサー
- 情報工学
- ヒープソートについて
ヒープでは親子関係を考えると親が子より小さい値をとりますよね。 それとは逆にヒープソートでは親が子より大きい値をとるとなっていますが何故でしょうか？ ヒープソートもヒープと同様に親が子より小さい値をとると何か不便なのでしょうか？
- ベストアンサー
- その他（プログラミング・開発）
- ヒープの探索の再帰
A[N]を利用したヒープのプログラムを作りました。 A[i]の親は、A[(i-1)/2]であるヒープです。 （上に行くほど小さい整数を格納） そしていまある整列されたヒープのなかからキーボードから入力した値ｘを検索する関数findを、 x ←検索する値 A[]←ヒープソートされた配列 n ←格納されているA[]の最後の添え字 として、 int find(int x, int *A, int i, int n) { if(A[i]==x){ printf("*\n"); /* ここの作業が行われているかを確認 */ return 1; } if(i>n)return 0; if(A[i]>x){ return 0; } else if (A[i]<x){ i = 2*i + 1; find(x, A, i, n); i++; find(x, A, i, n); } return 0; } というものを作ってみました。汚いかもしれませんが、とりあえず今はこれでいっぱいいっぱいです。 それで、当然のごとくうまくいきませんでした。 /**/内に書いたように、入力したｘがヒープ内にある場合は「*」が一応表示されるのですが、どうもfindは１を返してくれません。0を返してしまいます。見つけた後もまだ再帰をくりかえしえしているようです。 どこがいけないのでしょうか。
- ベストアンサー
- C・C++・C#
- ヒープソートは２重ソートできない？
ソートに関して詳しい方、相談にのっていただけたらと思います。 ＣＧＩを使ってヒープソートするロジックを組みました。 そのルーチンはただ単項データをソートするだけでなく、たとえば、配列変数 n1 と 配列変数 n2 にそれぞれデータが入っていたとき、n1 をソートすると、それに連動して n2 の中身も一緒にソートされます。 言うならば、バラバラに並んだビデオテープを番号順に並べ替えると、一緒にタイトルも並べ変わる感じです。 ところが、配列 n1 をソートしていてたまに同じ数字が入っていることがあります。そういうときは n2 の順にしたいのです。 そこで、先に n2 をソートしてから n1 をソートするといいのではと考え、そのようにプログラムを組んでみました。 ところが実際には、n1 をソートした瞬間に、せっかく並べ替えた n2 の内容がバラバラになってしまうのです。 「n1 の内容が同じ場合は n2 を昇順に並べる」という処理を記述していても、実際には n2 の内容はバラバラです。 これはヒープソートを使用している限り仕方のないことなのでしょうか。あるいは何らかの解決方法を知っている方、よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- シェルソートの順位性
このカテゴリーのNo.137（#35189）の続きなのですが、シェルソートについてご存知の方お願いします。 上記の質問にて、ヒープソートは完全二分割木型で、同一の値であってもその順序は保証されない、ということがわかりました。 そこで、配列の内容をソートする処理をシェルソートで組んでみました。 やろうとしているのは、n1、n2 の２つの配列に値を入れ、n1 が同じ値だったら n2 の値を使ってソートする、という処理です。 しかし実際には、n3、n4と無制限に続く２次元配列なので各配列を個別にソートしなければならず、n2 を先にソートしてから n1 をソートする、という処理を入れています。 ところがこれだと、n1 のソート時に同一の値の順序が崩れると、せっかく行った n2 のソートが無駄になってしまいます。 シェルソートの場合、こういうことは起こるのでしょうか。 よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- Perlのハッシュ変数のソートについて
ハッシュ変数の並べ替えをやりたいです。ただ、値の長さでソートをしたいのです。 my %tan_syouhin = ( '佐賀' => 'あいうえお', '滋賀' => 'かき', '無我' => 'さしすせそそそ', '千賀' => 'うりるら', '日我' => 'ぜるだんぽ' ); というハッシュ変数があって「値の長さ」でソートするにはどうしたら良いでしょうか？
- ベストアンサー
- Perl
- SQLについて
A B -------------------------------------------- 1111111 22222222222 -------------------------------------------- nullまたはブランク 33333333333 -------------------------------------------- 12121212 nullまたはブランク -------------------------------------------- 上記のようなレコードがあります。（A,Bはカラム名） 並べ替えを行いたいのですが、条件があります。 カラム名Aをキーにして並べ替えを行いたいのですが、 もしカラム名Aにデータがない場合は、変わりにBのデータを使用して並べ替えを行いたい、というものです。上記の場合、この条件で並べ替えるときは、1レコード目のAの値と、2レコード目のBの値、3レコード目のAの値でソートしたいということになります。このような並べ替えの方法をご存知の方がいらっしゃいましたら、ご教授ください。大変困っています。 DB:ORACLE8
- ベストアンサー
- Oracle
- ヒープソートの問題について
分からない問題があります。 どなたかお教え下さい。よろしくお願いします。 Max-Heapify (A,i) 1. L <- 2i 2. R <- 2i+1 3. if L<= heap-size[A] かつ A[L] > A[i] 4. then largest <- L 5. else largest <- i 6. if R<= heap-size[A] かつA[R] > A[largest]) 7. then largest <-R 8. if largest !=i 9. then 値の交換A[i] <-> A[largest] 10. Max-Heapify (A,largest) Build-Max-Heap (A) 1. heap-size[A] <- length[A] 2. for i<- ⌊length[A] /2⌋ downto 1 3 do Max-Heapify (A,i) Heap-Sort (A) 1. Build-Max-Heap (A) 2. for i<- length[A] downto 2 3 do 値の交換 A[1]<->A[i] 4 heap-size[A] = heap-size [A] – 1 5 Build-Max-Heap (A) 上に示す疑似コードを参考に、以下の問いに答えなさい。ただし、length[A]、heap-size[A]は配列Aの要素数、配列Aに格納されているヒープの要素をそれぞれ示す。 a. ヒープに格納される要素数をnとし、要素の添字の範囲を求めなさい。 b. 配列A=<3,9,8,15,4,2,5,1,7,10>からBuild-Max-Heapによりmax-ヒープを生成したときの結果を示しなさい。 c. 上のHeapsortは、配列を正しくソートするか？しないなら、正しくソートするようにするにはどのように修正すればよいか？理由と共に答えなさい。 d. マージソートと比較してヒープソートの良い点を述べなさい。
- 締切済み
- 科学
お礼
ありがとうございました。 やっぱりロジックで作るんですね^^;