fork download
copy 
  1. // heap-ki
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. #define height 4
  7. #define MAX (1<<height)  //ビットシフト演算 2^height と同じ
  8.  
  9. int t[MAX+1]; //配列外アクセス防止のためのダミーで＋１
  10. int sz = 0;
  11.  
  12. void swap(int *x, int *y){
  13.     int tmp = *x;
  14.     *x = *y;
  15.     *y = tmp;
  16. }
  17.  
  18. void initTree(int n){
  19.     int i;
  20.     for(i=0;i<MAX;i++){
  21.         t[i] = -1;
  22.     }
  23. }
  24.  
  25. void printA(){
  26.     int i;
  27.     for(i=1;i<=sz;i++) printf("%d ",t[i]);
  28.     printf("\n");
  29. }
  30.  
  31. void printT(int i){
  32.     int x = i;
  33.     while(x/2!=0){
  34.         printf("  ");
  35.         x/=2;
  36.     }
  37.     printf("%d\n",t[i]);
  38. }
  39.  
  40. int goP(int i){
  41.     if(i/2 == 0) return 0;
  42.     else return i/2;
  43. }
  44.  
  45. int goL(int i){
  46.     if(2*i >= MAX) return 0;
  47.     else return 2*i;
  48. }
  49.  
  50. int goR(int i){
  51.     if(2*i+1 >= MAX) return 0;
  52.     else return 2*i+1;
  53. }
  54.  
  55. void preOrder(int i){
  56.     if(t[i] == -1) return;
  57.     printT(i);
  58.     preOrder(goL(i));
  59.     preOrder(goR(i));
  60. }
  61.  
  62. void inOrder(int i){
  63.     if(t[i] == -1) return;
  64.     inOrder(goL(i));
  65.     printT(i);
  66.     inOrder(goR(i));
  67. }
  68.  
  69. void postOrder(int i){
  70.     if(t[i] == -1) return;
  71.     postOrder(goL(i));
  72.     postOrder(goR(i));
  73.     printT(i);
  74. }
  75.  
  76. void insBT(int x){
  77.     int k,i = 1;
  78.     for(k=0;k<height;k++){
  79.         if(t[i]==-1){
  80.             t[i] = x;
  81.             sz++;
  82.             return;
  83.         }
  84.         if(x < t[i]) i = goL(i);
  85.         else i = goR(i);
  86.     }
  87.     printf("Error : too high -> %d\n",x);
  88. }
  89.  
  90. //先頭の要素を取り出す
  91. //ダウンヒープ
  92. int popHeap(){
  93. int i=1;
  94. t[i] = -1; // 取り出して
  95.  
  96. swap(&t[1],&t[sz]); // 末尾の要素を根に持ってきて
  97.  
  98. sz=sz+1;
  99.  
  100. while(1){
  101. 	if(t[goL(i)]>t[goR(i)]){
  102. 		if(t[goL(i)]>t[i]){
  103. 			swap(&t[goL(i)],&t[i]);
  104. 			i = goL(i);
  105. 		}else{
  106. 			break;	
  107. 		}
  108. 	}else{
  109. 		if(t[goR(i)]>t[i]){
  110. 			swap(&t[goR(i)],&t[i]);
  111. 			i = goR(i);
  112. 		}else{
  113. 			break;	
  114. 		}
  115. 	}
  116. }
  117.  
  118. // 子のうちの大きい方と比較
  119. // 子の方が大きかったら交換
  120. // をHeapが完成するまで繰り返す
  121. // 事前学習資料のP.56～60
  122.  
  123.  
  124.  
  125. }
  126.  
  127. //末尾に要素を追加する
  128. //アップヒープ
  129. void pushHeap(int x){
  130. int i;
  131. sz = sz + 1;
  132. i=sz;
  133. t[i]=x;
  134.  
  135. while(1){
  136. 	if(i%2==0){
  137. 		if(t[i/2]<t[i]){
  138. 			if(i/2==1){
  139. 				swap(&t[i/2],&t[i]);
  140. 				break;
  141. 			}else{
  142. 				swap(&t[i/2],&t[i]);
  143. 				i = i/2;
  144. 			}
  145. 		}else{
  146. 			break;
  147. 		}
  148. 	}else{
  149. 		if(t[(i-1)/2]<t[i]){
  150. 			if((i-1)/2==1){
  151. 				swap(&t[(i-1)/2],&t[i]);
  152. 				break;
  153. 			}else{
  154. 				swap(&t[(i-1)/2],&t[i]);
  155. 				i = (i-1)/2;
  156. 			}
  157. 		}else{
  158. 			break;
  159. 		}
  160. 	}
  161. }
  162.  
  163.  
  164.  
  165. // 末尾に追加
  166. // 親と比較して、子の方が大きかったら交換
  167. // をHeapが完成するまで繰り返す
  168.  
  169.  
  170.  
  171.  
  172. }
  173.  
  174. int main(void){
  175.     int i,x,n;
  176.     scanf("%d",&n);
  177.     // 木の初期化
  178.     initTree(n);
  179.     for(i=0;i<n;i++){
  180.         scanf("%d",&t[i+1]);
  181.     }
  182.     sz = n;
  183.     // 中間順で表示
  184. 	inOrder(1);
  185.  
  186. 	// pop
  187. 	int a=popHeap();
  188. 	printf("pop : %d\n",a);
  189. 	inOrder(1);
  190.  
  191. 	a = popHeap();
  192. 	printf("pop : %d\n",a);
  193.  
  194. 	inOrder(1);
  195.  
  196. 	printf("push : 100\n");
  197. 	pushHeap(100);
  198. 	inOrder(1);
  199.  
  200. 	printf("push : 30\n");
  201. 	pushHeap(30);
  202. 	inOrder(1);
  203.     return 0;
  204. }
  205.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
12
89 34 55 13 16 21 32 2 3 4 5 8
stdout
copy 
      2
    13
      3
  34
      4
    16
      5
89
      8
    21
  55
    32
pop : 0
      2
    13
      3
  34
      4
    16
      5
55
    21
  32
    8
pop : 0
      2
    13
      3
  16
      4
    5
34
    21
  32
    8
push : 100
      2
    13
      3
  16
      4
    5
100
    21
  34
    32
      8
push : 30
      13
    16
      3
  30
      4
    5
100
    21
  34
    32
      8
https://ideone.com/mwcVDx
language:
C (gcc 8.3)
created:
7 hours 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!