- ベストアンサー
ヒープソートについて
ヒープでは親子関係を考えると親が子より小さい値をとりますよね。 それとは逆にヒープソートでは親が子より大きい値をとるとなっていますが何故でしょうか？ ヒープソートもヒープと同様に親が子より小さい値をとると何か不便なのでしょうか？
- sohiro
- お礼率90% (9/10)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数2
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (1)
- imogasi
- ベストアンサー率27% (4737/17068)
上へ（親へ）繰り上げるルールを、大きい方とするか、小さい方にするかは、ユーザーが、昇順を指定するか、降順を指定するかで、変える必要があります。 どちらもあり得るということです。教科書の例題などでは、昇順の場合だけを取り上げていることが多いため、ご質問が出るのでしょう。 ＞ヒープでは親子関係を考えると親が子より小さい値をとりますよね。 これも、大小どちらでも、「１つの」ヒープを考えている間、どちらかに統一して考えれば良いことです。 ○＜教訓＞全て教科書的な本などの説明は、判りやすい例 、簡単な例、１つの例を取り上げる傾向がある。 そのような本を見つづけていると、それだけが真理と思いやすい。いつも「他の例では」、「逆では」成り立つか、「実際は複雑なものの、どこを簡略化・簡単な例にしたか」をチェックしましょう。
お礼
両方あるんですね。知りませんでした。 ありがとうございました。
関連するQ&A
- ヒープって・・・？
ヒープソートなんかで使いますが、ヒープそのものはどうやって作るんですか？ ルートに最大の値が来て・・・ってのは解ってるのですが、そんな並べ替えをロジックでやってたら、ヒープを作る前にソートできてますよね？^^; ヒープってやつに値を入れたら勝手に並ぶんですか？
- ベストアンサー
- その他([技術者向] コンピューター)
- ヒープソートの問題について
分からない問題があります。 どなたかお教え下さい。よろしくお願いします。 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. マージソートと比較してヒープソートの良い点を述べなさい。
- 締切済み
- 科学
- ヒープソート 追加操作について
配列を用いたヒープにデータを追加する。 この際、データの追加は配列の最後の要素に新たなデータを加え、ヒープ条件を満足するまで 親子間でデータの交換を行う。 要素数をnとしたら、この追加操作にかかる最悪時間計算量を求めよ。 この問題なのですが、ただ単にデータを一つ追加する際の最悪時間計算量だったら、 オーダlog n ですが、 追加する要素がnこだったら、n* log nになります。 この問題ではどちらがより適切なのでしょうか？ どなたかご教授ください。
- 締切済み
- C・C++・C#
- 【ヒープの作り方】
データ構造やアルゴリズムについての質問です。 「ヒープ」を用いてソートができたりすること、 ヒープへ挿入や、ヒープからの削除は分かるのですが、 そもそもヒープの作り方が分かりません。 ≪作り方≫ ある要素の集合が与えられたとき、 １つ目の値をルートにもってくる ２つ目の値をルートと比較し、子≦ルートとなるように追加 ３つ目の値をルートと比較し、子≦ルートとなるように追加 ４つ目の値をルートの左の子と比較し、子≦ルートの左の子、かつルートとも比較 ..... という風に要素の集合から要素がなくなるまで続けるので正しいでしょうか？ それとも初めに与えられた要素の集合を ひとまず要素数分の２分木構造に割り当て、 ヒープが成り立つように、あとから値の交換を 行うのでしょうか？ いま、要素の集団は配列のように順番が決まっているとして 考えています。 ≪取り出しと削除≫ 値の「取り出し」と「削除」は別物。という認識は正しいでしょうか？ (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#
- 最小ヒープソートについて
問題：numbers.datから１０個の整数を読みこみヒープソートで昇順に表示せよ。 numbers.dat 91 63 71 14 60 1 24 13 80 15 質問：下記が自分のコードなんですが実行すると 1 13 13 13 13 13 13 13 13 13になるんですが、何を直せばいいでしょうか。最小の値を取り出していくようにしているつもりなんですが #include<stdio.h> #include<stdlib.h> void insert( int i,int a[], int n); int deletemin(int a[], int n,int m); int main() { int a[10],m[10]; int i,j,k; int n = 10; FILE *fp; fp = fopen("numbers.dat", "r"); if(fp == NULL) { printf("ファイルが開けません\n"); return 1; } fscanf(fp,"%d %d %d %d %d %d %d %d %d %d\n",&a[0] ,&a[1] ,&a[2] ,&a[3] ,&a[4] ,&a[5] ,&a[6] ,&a[7] ,&a[8],&a[9] ); for(i = (n - 2)/2; i >= 0; i--) { insert(i, a, n-1); } for(i = n-1; i >= 0; i-- ) { m[9-i] = deletemin(a, i, n-1); } for(j = 0; j < 10; j++){ printf("%3d",m[j]); } return 0; } void insert( int i,int a[], int n) { int j; int temp; while (2 * i + 1 <= n) { j = 2 * i + 1; if (j < n) { if (a[j] > a[j + 1]) { j++; } } if (a[i] <= a[j]) { break; } temp = a[j]; a[j] = a[i]; a[i] = temp; i = j; } } int deletemin(int a[],int n, int m) { int b; int temp; int i,j; b = a[0]; a[0] = a[n]; i = 0; while (2 * i + 1 <= m) { j = 2 * i + 1; if (j < m) { if (a[j] > a[j + 1]) { j++; } } if (a[i] <= a[j]) { break; } temp = a[j]; a[i] = a[j]; a[i] = temp; i = j; } return b; }
- 締切済み
- C・C++・C#
- 親windowから子windowのsubmit方法を教えて下さい。
親画面から、子画面を開きます。 子画面では、SELECTboxが二つありDBから読み込んだデータが表示されているのと、そこから選択されたデータを表示してるSELECTBOXがあります。 その選択されたSELECTBOXの値を親画面に渡しているのですが、今回その子画面に新規データを登録できるようにしたいのです。 データをINSERTする為に、子画面をsubmitする事で、SELECTBOXに追加とINSERTは出来ています。 しかし、子画面をsubmitしたことによって、親子関係が消えてしまい、親画面にデータを渡せません。 どうしたら良いか教えて頂けないでしょうか？ 宜しくお願いします。
- ベストアンサー
- JavaScript
- 「親ガチャ」何が悪い？
「親ガチャ」なんて言葉があるようです。 今風の言葉で面白いなと思ったのですが、どうも否定的な意見が 多いようで。何が悪いのでしょうか？ 親子関係ですと、以下のような言葉もあります。 「この親にしてこの子あり」 「子は親の鏡」 「子は親を選べない」 「親の顔が見たい」 「親も親なら子も子」
- ベストアンサー
- 人生相談
- 【認識調査】愛の関係を壊しているのは？
こんにちは。 以下、よろしくお願いします。 ある親子が居ます。 子がわがままに公共の場でけたたましい声を上げながら、近くに居る知人でも何でも無い家庭の子をいじめています。 この子は”ただ単に楽しんでいるだけ”でいじめているつもりはあまりなく、相手の気持ちも理解していないししようとも思っていません。 「単に自分が楽しいからしているだけ」です。 その親がこの子にこう言います。 あの子の事をいじめるんじゃない。かわいそうだろう。気持ちを考えなさい。etc。 当然、親は子に対する愛情に溢れていますし、このために言っていますが、完璧な人間ではないので表現方法、たとえば表情や声色などが「子を諭す親」として100点ではないかもしれません。 さて、子は親にこう思います。 「うるさいな～。楽しいんだから邪魔すんなよ」と。 そしていじめを継続できる様に色々な切り返しをします。 「その表情、愛情ではなくて単に感情的になってるだけだよね」「その声色、相手に恐怖感を与えるよ？」「それが愛情なの？」「信じられない」etc。 曲がりなりにも当然親は子に対して愛情を持っています。 が、子は親の気持ち等関係なく、自分がしたい事をしたいだけ。 この場合、親子の愛の関係を無としているのはどちらか、あるいは何か。 ※この質問の例は親子ですが、他人同士に置き換えても同じです。 よろしくお願い致します。
- 締切済み
- その他(恋愛・人生相談)
- エプソンのプリンタドライバの自動更新によってスクリーンが崩壊する問題が発生しています。
- 自動更新確認の画面が表示されるとスクリーン全体がずれたり消えたりし、ソフトウェアのフリーズやデータの保存不能などの問題が発生します。
- 自動更新を切ることで問題は解消されますが、なぜこのような現象が起きるのか疑問です。
お礼
昇順のソートか降順のソートかの違いでしたか… ありがとうございました。