みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

ヒープ deleteminの関数作成がわかりません

問題文:ヒープの最小値を取り除く、deletemin関数を作成せよ。空の配列にinsertを複数実行することでヒープ条件を満たすヒープを構成する。これにdeleteminを実行することで最小値を抽出せよ。最小値を抽出した後、一次元配列がヒープ条件を満たすように再構成せねばならない。プロトタイプ宣言は以下とする。
int deletemin(int a[], int *n);

質問:関数deleteminについて調べてはみたんですが何をしているのか分からないものばかりだったので質問させてください。ヒープの最後のノードを根に持ってきて、右のノードと左のノードを比べて小さい値のノードの方と比較して最後から持ってきたノードの値の方が大きければ交換するというの繰り返して最小ヒープを再構成したいのですが、どうすればいいのかわかりません。サイトなどみても分からなかったのでど素人でも分かるように説明お願いします。
以下自分のソース

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int check_heap(int a[], int n);
void insert(int val, int a[], int *n);
int deletemin(int a[],int *n);

int main(void) {
int a[12] = {1,13,71,14,15,80,91,24,60,63};
int n;
int i;
int b,c;

srandom(time(NULL));

b = random() % 100 + 1;
n = 10;
insert(b, a, &n);
n = 11;
c = random() % 100 + 1;
insert(c, a, &n);

printf("%d\n", check_heap(a, 12));

deletemin(a, &n);


return 0;
}

int check_heap(int a[], int n) {
int i;
int m;
m = (n - 1) / 2;
for(i = 0; i < m; i++)
{
if(a[i] >= a[i * 2 + 1])
{
return 0;
}
if(a[i] >= a[i * 2 + 2]){
return 0;
}
}


if(n % 2 == 0){

if(a[(n - 1)/2] > a[n - 1]){

return 0;
}
}
return 1;

}

void insert(int val, int a[], int *n) {

int temp;
int i;

a[*n] = val;
i = *n;

while( 0 < i){

if(a[(i-1)/2] <= a[i])
{
break;
}

temp = a[(i-1) / 2];
a[(i-1) / 2] = a[i];
a[i] = temp;
i = (i - 1)/2;


}

}

int deletemin(int a[],int *n){

int b;
int i,j,k;

b = a[0];












return b;
}

投稿日時 - 2012-09-09 20:25:24

QNo.7689398

すぐに回答ほしいです

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(2)

ANo.2

http://okwave.jp/qa/q6896310.html

投稿日時 - 2012-09-12 16:38:34

ANo.1

URL参照。

参考URL:http://codezine.jp/article/detail/3864

投稿日時 - 2012-09-09 21:55:26

あなたにオススメの質問