#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};
typedef struct node Node;

void insert(int data);
Node *search(int key);
void preorder_traversal(Node *root);
void inorder_traversal(Node *root);
void postorder_traversal(Node *root);

Node *root = NULL;

/* データの追加 */
void insert(int data)
{
    Node *new = (Node *)malloc(sizeof(Node));   //新ノード生成
    Node *current,*parent;

    new->data = data;   //新ノードのメンバーへデータ設定
    new->left = NULL;
    new->right = NULL;

    if(root==NULL){  //ルートが空ならば
        root = new;
    }
    else{
        current = root; //ルートからスタート
        parent = NULL;
        while(1){
            parent = current;   //親を設定
            //左の枝へ追加(小さい値)
            if(data < parent->data){
                current = current->left; //左ノードへ移動
                if(current == NULL){
                    parent->left = new; //左ノードが空なら新規ノード追加
                    return ;
                }
            }
            //右の枝へ追加(大きい値)
            else{
                current = current->right; //右ノードへ移動
                if(current == NULL){
                    parent->right = new;    //右ノードが空なら新規ノード追加
                    return ;
                }
            }
        }
    }
}

/* 探索 */
Node *search(int key)
{
    Node *current = root;   //ルートからスタート
    
    printf("Visiting: ");

    while(current->data != key){
        if(current != NULL) printf("%d -> ", current->data);

        //左側探索
        if(current->data > key)
            current = current->left;
        //右側探索
        else
            current = current->right;

        //探索失敗(
        if(current == NULL) return NULL;
    }
    return current;
}

/* 巡回(行きがけ) */
void preorder_traversal(Node *root)
{
    if(root != NULL){
        printf("%d ",root->data);
        pre_order_traversal(root->left);
        pre_order_traversal(root->right);
    }
}

/* 巡回(通りがけ) */
void inorder_traversal(Node *root)
{
	    /***
	       ここを埋めて完成させる
	    ***/
}

/* 巡回(帰りがけ) */
void postorder_traversal(Node *root)
{
	    /***
	       ここを埋めて完成させる
	    ***/
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define swap(x,y) { int tmp=x; x=y; y=tmp; }
#define MAX 32

void ins_node(int value);
void del_node(void);
void build_heap(void);
void heapify_max(int i);
void heapify_min(int i);
void shift_up(int index);
void heap_down(int index);
int is_empty(void);
void print_tree(void);

//int a[MAX] = {0};
int a[MAX] = {0,21,12,8,65,22,40,34,17,7,0,};
int heapsize=9;

/* 乱数によるデータ生成 */
void init_data(int n)
{
	int i;

	if(n>=MAX){
		 printf("N is over max number.\n");
		exit(EXIT_FAILURE);
	}
	srand((unsigned)time(NULL));
	for(i=1; i<n; i++)
		a[i] = rand()%50+2;	
}

/* ヒープ化 */
void build_heap(void)
{
	int i = heapsize/2;    //右下端部分木からスタート

	while(i>0)
		heapify_min(i--); //ルートまで繰り返す
}

/* ヒープ化(rootへ最小値を) */
void heapify_min(int i)
{
	int smallest = i;	//親
	int left = smallest;	//左の子
	int right = smallest;	//右の子

	if(a[i*2]) left = i*2;
	if(a[i*2+1]) right = i*2+1;

	if(left <= heapsize && a[left] <a[i]) smallest = left;	//左子>親?
	if(right <= heapsize && a[right] < a[smallest]) smallest = right;	//右子>(左、親)
	if(smallest != i){	//最大が親でなければ交換
		swap(a[i],a[smallest]);
		heapify_min(smallest);
	}
}

/* ノードの追加(右下端) */
void ins_node(int value)
{
    if(heapsize>MAX){
        printf("Error: Heap array is overflow.\n");
        exit(EXIT_FAILURE);
    }
    else {
        heapsize++;
        a[heapsize]=value;  //右下端に追加
        shift_up(heapsize); //再ヒープ(シフトアップ)
    }
}

/* シフトアップ
   ノード追加による
   右下端から上に向かってヒープ(ルート最小) */
void shift_up(int i)
{
    int parent,tmp;

    if(i != 0){
        parent = i/2; //親
        if(a[parent] > a[i]){ //親の方が大きければ
           swap(a[parent],a[i]);  //交換
           shift_up(parent);  //再帰的にヒープ
        }
    }
}

/* ノードの削除(root) */
void del_node(void)
{
    if(is_empty())
    {
        printf("Heap is empty.\n");
        exit(EXIT_FAILURE);
    }
    a[1] = a[heapsize];
    heapsize--;

    if(heapsize>0) heap_down(1);
}

/* ヒープダウン
   ノード削除による
   ルートから下に向かってヒープ（ルート最小） */
void heap_down(int i)
{
    int smallest;   //左右の子の小さい方の添字
    int left = i*2;       //left child index
    int right = left+1;  //right child index
    
    if(right>heapsize){	//右に子が無い
        if(left>heapsize)	//左右に子が無い
            return;
        else
            smallest = left; //左側の子しか無い場合
    }
    else {
        if(a[left]<=a[right])  //左右の子のうち小さい方は
            smallest = left;
        else
            smallest = right;
    }

    if(a[i] > a[smallest]){     //子の方が小さければ
        swap(a[i],a[smallest]);
        heap_down(smallest);       //下に移動
    }
}

/* 木構造の表示 */
void print_tree(void)
{
	int i,j,k;
	int count=1,height,ns,smax;
	int sidespace,space;

	height = (int)(log(heapsize)/log(2))+1;	//木の高さ 

	for(i=0; i<height; i++){		//レベル
		sidespace = pow(2,height-i-1)-1;
		for(k=0; k<sidespace; k++) printf("  ");	//左側空白
		space = pow(2,height-i)-1;
		ns = pow(2,i);
		for(j=0; j<ns && count<=heapsize; j++){	//レベルの最大数
			printf("%2d",a[count++]);
			for(k=0; k<space && j+1<ns; k++)
				if(j%2) printf("  "); else printf("--");	//空白
		}
		printf("\n");
	}
	printf("\n");
}

/* 空か？ */
int is_empty(void)
{
	return !heapsize;
}

int main(void)
{
	printf("[Before]\n");
    print_tree();

	printf("[Heap(min)]\n");
    build_heap();
    print_tree();

	printf("[Delete Node]\n");
    del_node();
    print_tree();

	printf("[Insert Node(10)]\n");
    ins_node(10);
    print_tree();
 
    return 0;
}