''갓원준님의 추월''
[[TableOfContents]]

= 참여자 명단 =

|| 함장 || 장용운 || 11학번 || 출석 ||
||<|4> 선원 || 천준현 ||<|4> 15학번 || 병결 ||
|| 박인서 || 출석 ||
|| 이원준 || 출석 ||
|| 남헌 || 출석 ||

= 수업 =
== 진행 ==
1. 장소 : 6층 학회실
2. 시간 : 15시 ~ 17시

== 내용 ==
'''수심 4000m. 트리2'''
 * 우선순위 큐(priority와 value 분리)
 * heapify
= 코드 =
== 예제1 ==

= 숙제 =
1. 고통받기
2. 고통받기
3. 고통받기

----


= 숙제 제출 = 
== 천준현 ==

== 박인서 ==

== 이원준 ==
=== key가 따로있는 heapmax ===
{{{
#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 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 (dir->var < input){
			temp_n = input;
			input = dir->var;
			dir->var = temp_n;
			temp_name = name;
			name = dir->name;
			dir->name = temp_name;

		}
		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_name = name;
		name = dir->name;
		dir->name = temp_name;
	}
	temp->var = input;
	temp->name = name;
	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;
	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;

	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->Lnode->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;
		}
	}

}
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);
	for (i = 0; i < 6; i++){
		pop(PQhead);
	}
}
}}}

=== heapify ===
{{{
#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);
	}
}
}}}
== 남헌 ==

----
-----------------------------------
[활동지도/2015]
[자료구족발보쌈]