[C언어로 쉽게 풀어쓴 자료구조] 연습문제 9강

01 (1)

02 (1) 완전 이진 트리에 대응되는 번호를 붙일 수 있기에 배열의 인덱스에 넣을 수 있다.

03 (2) 

04 (1) 최소 히프 사용 시 오름차순 데이터 추출에 용이

05 (2)

06 2번 노드와 3번 노드중 더 작은 데이터를 가진 노드

07 ⌈log2 10⌉= 4

08, 09, 10, 13, 17 하단 손글씨 풀이 참조

 

 

11

typedef struct element {
	char todo[50];
	int key;
}element;

//max heap 코드 추가

int main(){
	char c;
	HeapType *h;
	h=create();
	init(h);
	while(c!='q'){
		printf("삽입(i), 삭제(d): ");
		scanf("%c",&c);
		if(c=='i'){
			element e;
			printf("할일: ");
			scanf("%s",e.todo);
			scanf("%c",&c);//공백 받기
			printf("우선순위: ");
			scanf("%d",&e.key);
			scanf("%c",&c); //공백 받기
			insert_max_heap(h,e);
		}
		else if(c=='d'){
			element e;
			e = delete_max_heap(h);
			printf("제일 우선 순위가 높은 일은 %s \n",e.todo);
			scanf("%c",&c);//공백 받기
		}
		else if(c=='q') break;
	}
	return 0;
}

 

12

최소 히프트리가 아니다. key값이 6인 노드가 더 작은 key값인 5를 담은 노드를 자식 노드로 가지고 있다.

 

15

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
#define SIZE 8


typedef struct HeapType{
	int data;
	struct HeapType* link;
}HeapType;


HeapType* create_node(int data) {
	HeapType* new_node;
	new_node = (HeapType*)malloc(sizeof(new_node));
	new_node->data = data;
	new_node->link = NULL;
	return new_node;
}

void insert_max_heap(HeapType** phead, HeapType* new_node) {
	new_node->link = *phead; // NULL 아님
	*phead = new_node;
}
int delete_max_heap(HeapType** phead){
	if(*phead==NULL){
		printf("heap이 빔\n");
		return -1;
	}
	int max = 0;
	int temp;
	HeapType *target;
	HeapType *p = *phead;
	HeapType *prev = *phead;
	for(HeapType *node = p; node !=NULL;node = node->link){
		if(node->data > max){
			max = node->data;
			target = node;
		}
	}
	if(target == p){//최우선순위 노드가 헤드노드면
		*phead = p->link; // 헤드 교체
		free(target);
		return max;
	}
	else{
		while(prev->link !=target){
			prev=prev->link;
		}
		prev->link = target->link;
	}
	free(target);
	
	
	return max;
}

void print_list(HeapType* phead){
	for(HeapType *p = phead; p!=NULL;p= p->link){
		printf("%d->",p->data);
	}
	printf("NULL \n");
}


int main(){
	HeapType *head = NULL;
	for(int i=0; i<5;i++){
		HeapType *temp = create_node(i);
		insert_max_heap(&head,temp);
		print_list(head);
	}
	
    int deleted_value = delete_max_heap(&head);
    printf("우선순위 큐 삭제 data: %d\n", deleted_value);
    print_list(head);
	return 0;
}

 

16

void delete_min_heap(HeapType *h,int key){
	int parent, child;
	element item, temp;
	
	for(int i=1;i<h->heap_size;i++){
		if(h->heap[i].key ==key){
			parent = i;
			child = 2*i;
			break;
		}
	}
	item = h->heap[parent]; // 삭제할 노드는 바뀐 parent
	temp = h->heap[(h->heap_size)--];
	
	while(child <= h->heap_size){
		if((child<h->heap_size)&&(h->heap[child].key > h->heap[child+1].key)){
			child ++;
		} 
		if(temp.key<=h->heap[child].key) break;
		
		h->heap[parent] =h->heap[child];
		parent = child;
		child *=2;
	}// whlie문을 빠져나오면 parent 위치가 확정됨
	h->heap[parent] = temp;
}