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

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

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

void down(node *dir){
	char* name;
	int temp;

	if (dir->Lnode != NULL){
		down(dir->Lnode);
		if (dir->Rnode != NULL){
			down(dir->Rnode);
		}
	}

	if (dir->Lnode == NULL){
		return;
	}
	else if (dir->Rnode == NULL){
		if (dir->Lnode->var < dir->var){
			temp = dir->Lnode->var;
			dir->Lnode->var = dir->var;
			dir->var = temp;
			name = dir->Lnode->name;
			dir->Lnode->name = dir->name;
			dir->name = name;
		}
	}
	else if (dir->Lnode->var < dir->Rnode->var && dir->Lnode->var < dir->var){
		temp = dir->Lnode->var;
		dir->Lnode->var = dir->var;
		dir->var = temp;
		name = dir->Lnode->name;
		dir->Lnode->name = dir->name;
		dir->name = name;
	}
	else if (dir->Rnode->var < dir->Lnode->var && dir->Rnode->var < dir->var){
		temp = dir->Rnode->var;
		dir->Rnode->var = dir->var;
		dir->var = temp;
		name = dir->Rnode->name;
		dir->Rnode->name = dir->name;
		dir->name = name;
	}
}

void heapify(PQ *head){

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

	node *dir = head->one;
	int num = head->num;
	int num1 = 0;

	down(dir);
}

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

	printf("%s\n", dir->name);

	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;
		name = dir->Lnode->name;
		free(dir->Lnode);
		dir->Lnode = NULL;
	}
	else{
		temp = dir->Rnode->var;
		name = dir->Rnode->name;
		free(dir->Rnode);
		dir->Rnode = NULL;
	}
	(head->num)--;
	dir = head->one;
	dir->var = temp;
	dir->name = name;

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

}

void push(PQ *head, char *name, int input){
	node *temp = (node*)malloc(sizeof(node));
	int temp_n;
	char *temp_name;
	int past;
	int i, j;

	temp->Lnode = NULL;
	temp->Rnode = NULL;

	if (head->num == 1){
		temp->var = input;
		temp->name = name;
		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 (past % 2 == 0){
			dir = dir->Lnode;
		}
		else{
			dir = dir->Rnode;
		}
	}
	

	temp->var = input;
	temp->name = name;
	if (head->num % 2 == 0){
		dir->Lnode = temp;
	}
	else{
		dir->Rnode = temp;
	}
	(head->num)++;
}


int main(){
	PQ *PQhead = (PQ *)malloc(sizeof(PQ));
	int i;
	PQhead->num = 1;

	push(PQhead, "천준현", 2);
	push(PQhead, "남헌", 9);
	push(PQhead, "박인서", 8);
	push(PQhead, "이원준", 10);
	push(PQhead, "유재범", 2);
	heapify(PQhead);

	for (i = 0; i < 6; i++){
		pop(PQhead);
	}
}