fork download
copy 
  1. /*
  2. http://d...content-available-to-author-only...o.jp/qa/question_detail/q14117785524
  3. このコードの流用による不具合の責任を上記URLの回答者・質問者・サイト
  4. 運営者に問うことはできません。
  5. */
  6. #include<stdio.h>
  7.  
  8. #define MAX 10
  9. static int check_heap(int a[],int n);
  10. static void insert(int val,int a[], int* N);
  11. static void swap(int* a,int* b);
  12. static int deletemin(int a[], int *n);
  13.  
  14. int main(void){
  15. int dat[MAX]={41,13,29,96,7,86,4,10,90,64};
  16. int heap[MAX];
  17. int i,result;
  18. int n=0;
  19. int min;
  20.  
  21. 	//関数呼び出し
  22. 	for(i=0;i<MAX;i++)insert(dat[i],heap,&n);
  23.  
  24. 	for(i=0;i<MAX;i++)printf("%d ",heap[i]);
  25. 	printf("\n\n");
  26.  
  27. 	while(n>0){
  28. 		min=deletemin(heap,&n);//関数呼びだし
  29. 		printf("ヒープの最小値は%dです\n",min);
  30. 		for(i=0;i<MAX;i++)printf("%d ",heap[i]);
  31. 		printf("\n");
  32. 		result=check_heap(heap,n);//関数呼びだし
  33. 		if(result==1)printf("ヒープ条件を満たしています.\n");else printf("ヒープ条件を満たしていません.\n");
  34. 		printf("\n");
  35. 	}
  36.  
  37.  
  38. 	return 0;
  39. }
  40.  
  41. //ヒープ条件を満たしているかチェックする関数
  42. int check_heap(int a[],int n){
  43. int i,left,right;
  44. 	for(i = 0; i < n; i++) {
  45. 		left=2*i+2;
  46. 		right=left+1;
  47. 		if(right<=n)if(a[right-1] < a[i]) return 0;
  48. 		if(left<=n)if(a[left-1] < a[i]) return 0;
  49. 	}
  50. 	return 1;
  51. }
  52.  
  53. //新しく値を挿入する関数
  54. void insert(int val,int a[], int* N){
  55. int n;
  56. 	a[(*N)++]=val;
  57. 	n=*N;
  58. 	while(n>1){
  59. 		if( a[n-1] > a[n/2-1] )break;
  60. 		swap(&a[n-1],&a[n/2-1] );
  61. 		n/=2;
  62. 	}
  63. }
  64.  
  65. //値を入れ替える関数
  66. void swap(int* a,int* b){
  67. int temp;
  68. 	temp=*a;
  69. 	*a=*b;
  70. 	*b=temp;
  71. }
  72.  
  73. //ヒープの最小値を取り除く関数
  74. //負の値を返した場合は*N<=0
  75. int deletemin(int a[], int *N){
  76. int result;
  77. int n;
  78. 	if(*N<=0)return -1;
  79. 	result=a[0];
  80. 	swap(&a[0],&a[*N-1]);
  81. 	(*N)--;
  82. 	n=1;
  83. 	while(n<=*N){
  84. 		if(2*n>*N)break;
  85. 		if(2*n+1<=*N){
  86. 			if(a[2*n]<a[2*n-1]){
  87. 				if(a[2*n]<a[n-1]){
  88. 					swap(&a[2*n],&a[n-1]);
  89. 					n*=2;
  90. 					n++;
  91. 					continue;
  92. 				}
  93. 			}
  94. 		}
  95. 		if(a[n-1]>a[2*n-1]){
  96. 			swap(&a[n-1],&a[2*n-1]);
  97. 			n*=2;
  98. 			continue;
  99. 		}
  100. 		break;
  101. 	}
  102. 	return result;
  103. }
Success #stdin #stdout 0s 2292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4 10 7 13 41 86 29 96 90 64 

ヒープの最小値は4です
7 10 29 13 41 86 64 96 90 4 
ヒープ条件を満たしています.

ヒープの最小値は7です
10 13 29 90 41 86 64 96 7 4 
ヒープ条件を満たしています.

ヒープの最小値は10です
13 41 29 90 96 86 64 10 7 4 
ヒープ条件を満たしています.

ヒープの最小値は13です
29 41 64 90 96 86 13 10 7 4 
ヒープ条件を満たしています.

ヒープの最小値は29です
41 86 64 90 96 29 13 10 7 4 
ヒープ条件を満たしています.

ヒープの最小値は41です
64 86 96 90 41 29 13 10 7 4 
ヒープ条件を満たしています.

ヒープの最小値は64です
86 90 96 64 41 29 13 10 7 4 
ヒープ条件を満たしています.

ヒープの最小値は86です
90 96 86 64 41 29 13 10 7 4 
ヒープ条件を満たしています.

ヒープの最小値は90です
96 90 86 64 41 29 13 10 7 4 
ヒープ条件を満たしています.

ヒープの最小値は96です
96 90 86 64 41 29 13 10 7 4 
ヒープ条件を満たしています.
https://ideone.com/L0by1D
language:
C (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!