힙 생성 복습 (3주차)

힙 :  힙 조건을 만족하는 완전 이진 트리

완전 이진 트리 :  다음 2가지 조건을 만족하는 이진 트리
1. 마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 함
2. 마지막 레벨의 노드들은 왼쪽부터 차례대로 채워져 있어야 함

---

힙 삽입 :  
(배열) 새로운 요소를 맨 뒤에 추가(n값 1 증가시키고 키값 추가)  +  Upheap으로 힙 순서 복구
(연결리스트) 새로운 마지막 노드 z (외부노드) 찾기 + 키를 z 에 저장한 후 z 를 내부노드로 바꾸기 + Upheap으로 힙 순서 복구

힙 삭제 :  
(배열) 루트 키를 마지막 요소인 인덱스 n의 키로 대체  +  n값 1 감소시키기  +  Downheap으로 힙순서 복구
(연결리스트) 루트 키를 마지막 노드 w의 키로 대체(루트 키를 삭제) + w와 그의 자식들(외부노드)를 외부노드로 바꾸기 + Downheap으로 힙순서 복구

upHeap() 함수는 자식 노드 1개와 부모 노드끼리만 대소 비교를 하지만  (방향은 위 방향)
downHeap() 함수는 자식 노드 2개와 부모 노드 모두 대소 비교(레벨 비교)를 한다.  (방향은 아래방향)

---

힙 생성 방법 2가지
삽입식 :  1.모든 키들이 미리 주어진 경우 + 2.키들이 차례로 주어지는 경우 둘 다 가능

상향식(재귀, 비재귀 버전) :  1.모든 키들이 미리 주어진 경우만 가능
    재귀 버전 : 매개변수 없이 전부 다 downHeap 함
    비재귀 버전 : 매개변수 있어서 내가 설정한 인덱스까지 downHeap 함 
(2가지 버전 모두 밑에서부터 downHeap 하면서 올라가는 복구 방법)

---

힙 구현 방법 2가지
순차힙 : 배열을 이용한 순차트리 형태 

(어떤 노드 인덱스 : i ,  부모 노드 인덱스 : i / 2 ,  왼쪽 자식 인덱스 : i * 2 ,  오른쪽 자식 인덱스 : i * 2 + 1)
연결힙 : 연결리스트를 이용한 연결트리 형태

 

실습문제 1번 :  순차힙  +  최대힙  +  삽입식 코드  :  힙 키들을 하나씩 입력받는 방법

upHeap , downHeap , 삽입 함수 , 삭제 함수

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#pragma warning(disable:4996)

int H[100] = { 0 }, n = 0;


void upHeap(int i) {
	if (i == 1)                     // 해당 노드가 루트인 경우
	{
		return;
	}
	if (H[i] <= H[i / 2])          // 부모의 키 값이 자식보다 더 크면 정상
	{
		return;
	}
	int tmp;
	tmp = H[i];
	H[i] = H[i / 2];
	H[i / 2] = tmp;
    
	upHeap(i / 2);               // 다음 레벨로 올라가기
}

void downHeap(int i) {

	if (i * 2  > n)              // 자식이 없는 경우
		return;      

	int tmp, big = i * 2;       // big를 왼쪽 자식으로 고정

	if ((i*2 + 1) <= n && H[i*2 + 1] > H[big]) {   // big 를 오른쪽 자식으로 변경
		big = 2 * i + 1; 
	}

	if (H[i] >= H[big]) return;    // 부모의 키값이 자식보다 크면 정상

	tmp = H[i];
	H[i] = H[big];
	H[big] = tmp;
    
	downHeap(big);              // 다음 레벨로 내려가기
}

void insertItem(int key) {

	n += 1;
	H[n] = key;
	upHeap(n);
}

int removeMax() {

	int key;

	key = H[1];
	H[1] = H[n];
	n -= 1;
	downHeap(1);

	return key;
}

void printHeap() {
	for (int i = 1; i <= n; i++)
	{
		printf(" %d", H[i]);
	}
}

int main() {
	int key, removeKey;
	char command;

	while (1) {
		scanf(" %c", &command);

		if (command == 'i')
		{
			scanf("%d", &key);
			insertItem(key);
			printf("0\n");
		}
		else if (command == 'd')
		{
			removeKey = removeMax();
			printf("%d\n", removeKey);
		}
		else if (command == 'p')
		{
			printHeap();
			printf("\n");
		}
		else if (command == 'q')
		{
			break;
		}
	}

	return 0;
}

 

 

 

 

실습문제 2번 :  순차힙  +  최대힙  +  상향식 코드(비재귀 버전)  :  힙 키들을 한꺼번에 받는 방법

downHeap , 힙 생성 함수

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#pragma warning(disable:4996)

int H[100] = { 0 }, n = 0;


void downHeap(int i) {

	if (i * 2  > n) 
		return;

	int tmp, big = i * 2;   // 최대를 왼쪽 자식으로 고정

	if ((i*2 + 1) <= n && H[i*2 + 1] > H[big]) {
		big = 2 * i + 1;
	}
	if (H[i] >= H[big]) return;   // 3번

	tmp = H[i];
	H[i] = H[big];
	H[big] = tmp;
	downHeap(big);
}
void buildHeap() {
	for (int i = n/2; i > 0; i--)  // n/2부터, 밑에서부터 downHeap 하면서 올라가는 복구 방법
	{
		downHeap(i);
	}
}

void printHeap() {
	for (int i = 1; i <= n; i++)  
	{
		printf(" %d", H[i]);
	}
}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		scanf(" %d", &H[i]);
	}

	buildHeap();

	printHeap();
 

	return 0;
}

// 상향식 힙 생성의  재귀 버전

void rBuildHeap(int i){   // 인덱스 i 지정 가능
    if(i > n) 
       return;
    rBuildHeap(2i);
    rBuildHeap(2i + 1);   // 마지막 레벨까지 내려간 다음,
    downHeap(i);          // ***밑에서부터 downHeap 해서 힙 복구***
    return;
}