fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>	/* 疑似乱数生成時に必要 */
  3. #include <time.h>	/* 実行毎に異なる疑似乱数を発生させる為必要 */
  4.  
  5. /* マクロ定義 */
  6. #define NUM_DATA 16	/* 要素数 */
  7.  
  8. void SetDataB(int a[],int N)
  9. {
  10. 	int i;		/* ループカウンタ */
  11.  
  12. 	for (i = 0; i<N; i++) {
  13. 		a[i] = N-i-1;	/* 0以上100以下の整数乱数を生成 */
  14. 	}
  15. }
  16. void SetData_Fix(int a[], int N)
  17. {
  18. 	int i;		/* ループカウンタ */
  19. 	double rd;	/* [0,1)の実数乱数を格納する */
  20.  
  21. 	for (i = 0; i < N; i++) {
  22. 		rd = rand() / (RAND_MAX + 1.0);	/* [0,1)の実数乱数を生成 */
  23. 		a[i] = (int)(100 + 1) * rd;	/* 0以上100以下の整数乱数を生成 */
  24. 	}
  25. }
  26. void ShowData_Fix(int a[], int N)
  27. {
  28. 	int i;
  29.  
  30. 	for (i = 0; i < N; i++) {
  31. 		printf("%d, ", a[i]);
  32. 	}
  33. 	printf("\n");
  34. }
  35. void DownHeap_Fix(int a[],int k, int r)
  36. {
  37. 	int j;		/* ループカウンタ */
  38. 	int tmp;	/* 一時格納変数 */
  39.  
  40. 	j = 2 * k + 1;	/* 最初は(とりあえず)左の子の添え字番号をjに代入 */
  41. 	while (j <= r) {
  42. 		if ((j != r) && (a[j + 1] > a[j]))	/* j != r 左右両方の子供が存在するとき */
  43. 			/* j には左右の子のうち大きい方の添え字番号を代入 */
  44. 			j = j + 1;			/* a[j] とa[j + 1] を比較して大きい方をj とする */
  45. 		if (a[k] >= a[j]) {	/* a[k] がa[j] 以上ならば終了 */
  46. 			break;			/* whileループを抜ける */
  47. 		}
  48. 		else {	/* そうでなければ，a[k]とa[j]の値を入れ替え */
  49. 			tmp = a[k];
  50. 			a[k] = a[j];
  51. 			a[j] = tmp;
  52.  
  53. 			/* kとjの値を入れ替える */
  54. 			tmp = k;
  55. 			k = j;
  56. 			j = 2 * tmp + 1;	/* 左の子の添え字番号をjに代入 */
  57. 		}
  58. 	}
  59. }
  60. void InitializeHeap_Fix(int a[],int n)
  61. {
  62. 	int i;	/* ループカウンタ */
  63. 	int k;	/* ダウンヒープを開始する頂点番号 */
  64. 	int r;	/* ヒープの要素数 */
  65.  
  66. 	/* i = n / 2 - 1 初期値は親ノードの添え字を設定 */
  67. 	for (i = n / 2 - 1; i >= 0; i--) {
  68. 		k = i; 		/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  69. 		r = n - 1;	/* 現在のヒープの要素数- 1 */
  70. 		DownHeap_Fix(a,k, r);	/* ダウンヒープ */
  71. 		ShowData_Fix(a,n);		/* ダウンヒープの実行過程を表示 */
  72. 	}
  73. }
  74. void HeapMain_Fix(int a[], int n)
  75. {
  76. 	int i;			/* ループカウンタ */
  77. 	int k;			/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  78. 	int r;			/* ヒープの要素数 */
  79. 	int tmp;		/* 一時格納変数 */
  80.  
  81. 	if (n <= 0) return;
  82.  
  83. 	i = n - 1;		/* 末尾の要素の前の要素 */
  84. 	while (i >= 0) {
  85. 		tmp = a[0]; 	/* 根の値(※最大値になってるはず)と最後の頂点(末尾の要素)を入れ替える */
  86. 		a[0] = a[i];
  87. 		a[i] = tmp;
  88. 		i--;			/* 最後の頂点(末尾の要素)をヒープから除外する */
  89. 		k = 0; 			/* ダウンヒープを開始する頂点番号 */
  90. 		r = i;			/* 最後の頂点(末尾の要素)を除外した後のヒープ要素数 */
  91. 		DownHeap_Fix(a, k, r);	/* ダウンヒープ */
  92. 	}
  93. 	a += 2;
  94. 	n -= 2;
  95. 	InitializeHeap_Fix(a, n);
  96. 	HeapMain_Fix(a, n);
  97.  
  98. }
  99.  
  100.  
  101.  
  102.  
  103.  
  104. void StartA(int Data[], int N){
  105. 	InitializeHeap_Fix(Data, N);
  106. 	HeapMain_Fix(Data, N);
  107. 	puts("AfterA:");
  108. 	ShowData_Fix(Data, N);
  109. }
  110.  
  111. int main(){
  112.  
  113. 	int Data[NUM_DATA] = { 54, 41, 18, 31, 70, 17, 60, 89, 36, 98, };
  114. 	int N = 3;
  115.  
  116. 	SetDataB(Data, NUM_DATA);
  117.  
  118. 	puts("BeforeA:");
  119. 	ShowData_Fix(Data,NUM_DATA);
  120. 	puts("");
  121. 	StartA(Data+N,NUM_DATA-N*2);
  122.  
  123. 	puts("Result");
  124. 	ShowData_Fix(Data, NUM_DATA);
  125.  
  126. 	return 0;
  127. }
Success #stdin #stdout 0s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
BeforeA:
15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 

12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 
5, 6, 7, 12, 9, 10, 11, 8, 
5, 6, 11, 12, 9, 7, 10, 8, 
5, 12, 11, 9, 8, 7, 10, 6, 
12, 11, 9, 10, 8, 7, 6, 5, 
7, 8, 12, 10, 11, 9, 
7, 11, 12, 8, 10, 9, 
12, 9, 11, 8, 7, 10, 
9, 12, 11, 10, 
12, 11, 10, 9, 
12, 11, 
AfterA:
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 
Result
15, 14, 13, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 2, 1, 0,
https://ideone.com/tkX2ZE
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

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!