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

typedef struct node{
	int val;
	struct node* lnext;
	struct node* rnext;
}node;

void push(node *, int);
int find(node *);
int pop(node *);
void swap(int *,int *);
long cnt=1;

int main()
{
	int a;
	char ch[5];
	node head;
	printf("초기값 설정 ㄱㄱ\n");
	scanf("%d",&head.val);
	head.lnext=NULL;
	head.rnext=NULL;
	for(;;)
	{
		printf("push나 pop이나 exit 입력(push/pop/exit)\n");
		scanf("%s",ch);
		if(ch[0]=='e' && ch[1]=='x' && ch[2]=='i' && ch[3]=='t') break;
		else if(ch[0]=='p' && ch[1]=='u' && ch[2]=='s' && ch[3]=='h')
		{
			printf("넣을 숫자 입력 ㄱㄱ(자연수만) : ");
			scanf("%d",&a);
			push(&head,a);
		}
		else if(ch[0]=='p' && ch[1]=='o' && ch[2]=='p')
		{
			a=find(&head);
			if(a==-1) printf("숫자 없음\n");
			else printf("%d가 있었다\n",a);
		}
		else printf("push나 pop이나 exit만 입력하라고...\n");
	}
	return 0;
}
void swap(int * a, int * b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

void push(node * target, int newval)
{
	node * newnode;
	int a=1,c,i,temp,flag=0;
	int * b;
	cnt++;
	if(cnt==1)
	{
		target->val=newval;
		target->lnext=NULL;
		target->rnext=NULL;
		return;
	}
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	newnode=(node *)malloc(sizeof(node));
	temp=newval;
	for(i=c-2;i>=1;i--)
	{
		if(target->val>newval) swap(&target->val,&newval);
		if(b[i]==0) target=target->lnext;
		else target=target->rnext;
	}
	if(target->val>newval) swap(&target->val,&newval);
	newnode->val=newval,newnode->lnext=NULL,newnode->rnext=NULL;
	if(b[0]==0) target->lnext=newnode;
	else target->rnext=newnode;
	free(b);
}

int find(node * target)
{
	int res,regap;
	node * imsi=(node *)malloc(sizeof(node));
	imsi=target;
	res=pop(target);
	if(res==-1) return -1;
	target=imsi;
	regap=target->val;
	target->val=res;
	while(target->lnext!=NULL || target->rnext!=NULL)
	{
		if(target->lnext!=NULL && target->rnext!=NULL)
		{
			if(target->val>target->lnext->val && target->val>target->rnext->val)
			{
				if(target->lnext->val<=target->rnext->val)
				{
					swap(&target->val,&target->lnext->val);
					target=target->lnext;
				}
				else
				{
					swap(&target->val,&target->rnext->val);
					target=target->rnext;
				}
			}
			else if(target->val>target->lnext->val)
			{
				swap(&target->val,&target->lnext->val);
				target=target->lnext;
			}
			else if(target->val>target->rnext->val)
			{
				swap(&target->val,&target->rnext->val);
				target=target->rnext;
			}
			else break;
		}
		else if(target->lnext!=NULL)
		{
			if(target->val>target->lnext->val)
			{
				swap(&target->val,&target->lnext->val);
				target=target->lnext;
			}
			else break;
		}
		else if(target->rnext!=NULL)
		{
			if(target->val>target->rnext->val)
			{
				swap(&target->val,&target->rnext->val);
				target=target->rnext;
			}
			else break;
		}
		else break;
	}
	return regap;
}

int pop(node * target)
{
	int a=1,c,i;
	int * b;
	if(cnt==0) return -1;
	if(cnt==1)
	{
		cnt--;
		return target->val;
	}
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=1;i--)
	{
		if(b[i]==0)
			target=target->lnext;
		else
			target=target->rnext;
	}
	if(b[0]==0)
	{
		a=target->lnext->val;
		free(target->lnext);
		target->lnext=NULL;
	}
	else
	{
		a=target->rnext->val;
		free(target->rnext);
		target->rnext=NULL;
	}
	free(b);
	cnt--;
	return a;
}

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

typedef struct _node{
	struct _node *Rnode;
	struct _node *Lnode;
	int var;
} node;

typedef struct _PQ{
	node *one;
	int num; // num-1이 들어있는 갯수
} PQ;


void push(PQ *head, int input){
	node *temp = (node*)malloc(sizeof(node));
	int temp_n;
	int past;
	int i, j;
	
	temp->Lnode = NULL;
	temp->Rnode = NULL;

	if (head->num == 1){
		temp->var = input;
		head->one = temp;
		(head->num) += 1;
		return;
	}
	node *dir = head->one;
	int num = head->num;
	int num1 = 0;
	while (num != 1){
		num = num / 2;
		num1++;
	}

	for (j = 0; j < num1 - 1; j++){
		past = head->num;
		for (i = 0; i < num1 - 1 - j; i++){
			past = past / 2;
		}
		if (dir->var > input){
			temp_n = input;
			input = dir->var;
			dir->var = temp_n;
		}
		if (past % 2 == 0){
			dir = dir->Lnode;
		}
		else{
			dir = dir->Rnode;
		}
	}
	if (dir->var > input){
		temp_n = input;
		input = dir->var;
		dir->var = temp_n;
	}
	temp->var = input;
	if (head->num % 2 == 0){
		dir->Lnode = temp;
	}
	else{
		dir->Rnode = temp;
	}
	(head->num)++;
}

void pop(PQ *head){
	int i, j;
	int num = (head->num) - 1;
	int num1 = 0;
	int temp;
	node *dir = head->one;
	if (num == 0){
		printf("안돼 돌아가 없어!\n");
		return;
	}

	printf("%d\n", dir->var);

	if (num == 1){
		free(head->one);
		(head->num)--;
		return;
	}

	while (num != 1){
		num = num / 2;
		num1++;
	}
	for (j = 0; j < num1-1; j++){
		num = (head->num) - 1;
		for (i = 0; i < num1 -1 - j; i++){
			num = num / 2;
		}
		if (num % 2 == 0){
			dir = dir->Lnode;
		}
		else{
			dir = dir->Rnode;
		}
	}

	num = (head->num) - 1;
	if (num % 2 == 0){
		temp = dir->Lnode->var;
		free(dir->Lnode);
		dir->Lnode = NULL;
	}
	else{
		temp = dir->Rnode->var;
		free(dir->Rnode);
		dir->Rnode = NULL;
	}
	(head->num)--;
	dir = head->one;

	while(1){
		if (dir->Lnode == NULL){
			dir->var = temp;
			break;
		}
		else if (dir->Rnode == NULL){
			if (dir->Lnode->var < temp){
				dir->var = dir->Lnode->var;
				dir->Lnode->var = temp;
				break;
			}
			else{
				dir->var = temp;
				break;
			}
		}
		else if (dir->Lnode->var < dir->Rnode->var && dir->Lnode->var < temp){
			dir->var = dir->Lnode->var;
			dir = dir->Lnode;
		}
		else if (dir->Rnode->var < dir->Lnode->var && dir->Rnode->var < temp){
			dir->var = dir->Rnode->var;
			dir = dir->Rnode;
		}
		else{
			dir->var = temp;
			break;
		}
	}

}
int main(){
	PQ *PQhead = (PQ *)malloc(sizeof(PQ));
	int i;

	PQhead->num = 1;
	for (i = 0; i < 100; i++){
		push(PQhead, rand());
	}
	for (i = 0; i < 101; i++){
		pop(PQhead);
	}
}