質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.75%

  • C

    3448questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

ヒープソートを行う際、要素に重複があるとダウンヒープがうまくいかない

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 187

wassho1

score 1

 前提・実現したいこと

配列の要素に重複がある場合でもヒープソートを実現したい.

 発生している問題・エラーメッセージ

配列の要素に重複がある場合, 以下のような結果になります.

$ cat data1.txt
9
4
2
3
4
9
7
5
3
4
$ ./heap
input filename:data1.txt
4 2 3 4 9 7 5 3 4
2 3 4 4 3 5 4 7 9


data1.txtの1行目は要素の個数を表しているので関係はございません. 2行目以降がヒープソートを実行したい配列の要素になります.

 該当のソースコード

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int parent(int i);
int left(int i);
int right(int i);
int right(int i);
void Upheap_sort(int H[],int n);
void Build_Heap(int H[], int n);
void Downheap_sort(int H[], int n);
void heapsort(int H[],int n);

int main(void){
    int Data[50];/*数値を格納する配列*/
    int N;/*読み込む要素数*/
    int i;
    char fname[128];//読み込むファイルの名前をかくのうする変数
    FILE *fp;

    printf("input filename:");
    fgets(fname,sizeof(fname),stdin);//標準入力からファイル名を取得
    fname[strlen(fname)-1] = '\0';//最後の行改行コードを削除
    fflush(stdin);//128文字を超えた入力を標準入力から捨てる
    fp = fopen(fname, "r");//ファイルを読み込みモードで開く
    fscanf(fp,"%d",&N);
    for(i=0;i<N;i++){
    fscanf(fp, "%d",&Data[i]);
    }
    fclose(fp);

    for(i=0;i<N;i++){
    printf("%d ", Data[i]);
    }
    printf("\n");

    heapsort(Data,N);

    for(i=0;i<N;i++){
    printf("%d ", Data[i]);
    }
    printf("\n");

    return 0;
}

int parent(int i){//親を返す関数
    int ans;
    ans = (double)(i-1)/2;
    return ans;
}
int left(int i){//左の子を返す関数
    int ans;
    ans = 2*i+1;
    return ans;
}

int right(int i){//右に子を返す関数
    int ans;
    ans =2*i+2;
    return ans;
}

void Upheap_sort(int H[], int i){//一番後ろの要素をheapの性質を満たすように並べ替える関数.
    int u,tmp;
    u = i;
    while(u>0 && H[parent(u)]<H[u]){
    tmp = H[parent(u)];
    H[parent(u)] = H[u];
    H[u] = tmp;
    u = parent(u);
    }
}

void Build_Heap(int H[],int n){//heapをつくる関数
    int i;
    for(i=1;i<n;i++){
    Upheap_sort(H,i);
    }
}

void Downheap_sort(int H[],int n){//根の値をheapの性質にしたがって直す関数
    int u,l,r,tmp;
    u=0;
    l=1;
    r=2;
    while(l!=u && r!=u){//l=r=uとなれば終了
      if(left(u)<=n){//左の子がいるかいないかで場合分け
    l = left(u);
      }
      else{
    l = u;
      }
      if(right(u)<=n){//右も同様
    r = right(u);
      }
      else{
    r = u;
      }
      if(H[l]>H[u] || H[r]>H[u]){//H[l]もしくはH[r]のどちらかの値がH[u]の値を超えていたらこの操作に入る
    if(H[l]>=H[r]){//H[l]がH[r]以上ならば左の子とH[u]の値を交換
        tmp = H[u];
        H[u] = H[l];
        H[l] = tmp;
        u = l;
    }
    else{
      tmp = H[u];
      H[u] = H[r];
      H[r] = tmp;
      u = r;
    }
      }
      else{//H[l], H[r]がともにH[u]以下の場合このループをぬけ出す.
    l = u;
    r = u;
      }
    }
}

void heapsort(int H[],int n){//heapsort関数
    int i,tmp;
    Build_Heap(H,n);
    for(i=1;i<n;i++){
    tmp = H[n-i];
    H[n-i] = H[0];
    H[0] = tmp;
    Downheap_sort(H,n-i-1);
    }
}

 試したこと

ヒープをつくることは正常にできました.

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • set0gut1

    2018/05/12 14:45

    内容修正を期待しています

    キャンセル

  • wassho1

    2018/05/12 15:32

    私がteratailを使い慣れていないことが原因でご不便をお掛けしました. 申し訳ございません.

    キャンセル

  • set0gut1

    2018/05/12 15:40

    いえいえ、問題ありません。

    キャンセル

回答 2

check解決した方法

0

原因がわかり自己解決に至りました。Downheap_sortのwhileの条件文の論理演算子が「&&」ではなく「||」でないと、lもしくはrがuになった時点でwhile文から抜けてしまうためでした

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

こんにちは、
ヒープソートをご覧ください。

#include <stdio.h>

void h_down(int *ar,int size,int root);
void h_sort(int *ar,int size);
void swap(int *a, int *b);

int main(void){

    int ar[]={9,4,2,3,4,9,7,5,3,4};
    int ar_size = sizeof(ar) / sizeof(int) - 1;
    int i;
    h_sort(ar,ar_size);

    for(i = 0;i <= ar_size;i++){
        printf("%d ",ar[i]);
    }
    printf("\n");
    return 0;
}

void swap(int*a, int*b){ //入れ替え
    int c;
    c = *a;
    *a = *b;
    *b = c;
}

void h_sort(int*ar,int size){
    //ヒープ作成
    int i;
    for(i = (size / 2);i >= 0;i--){
        h_down(ar,size,i);
    }
    //ヒープソート
    while(1){
        swap(&ar[0],&ar[size--]);
        if(!size) break;
        h_down(ar,size,0);
    }
    return;
}

void h_down(int*ar,int size,int root)
{
    int max;
    while(1){
        //値の大きい方の枝を調べる
        max=root * 2 + 1;
        if(root * 2 + 2 <= size){//2の枝が存在する
            if(ar[root * 2 + 1]<ar[root * 2 + 2]){//1の枝と比較して
                max=root * 2 + 2;
            }
        }
        else if(!(root * 2 + 1 <= size)){
            break;//1の枝が存在しないため終了
        }
        //値の大きいほうの枝と根を比べて、値を交換する
        if(ar[root]<ar[max]){
            swap(&ar[root],&ar[max]);
            root = max;//交換できたため、枝←根にする
        }
        else{
             break;//根の方が大きいため終了
        }
    }
    return;
}


データ
9 4 2 3 4 9 7 5 3 4
結果
2 3 3 4 4 4 5 7 9 9

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.75%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C

    3448questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。