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