[힙과 힙정렬] 힙 생성 (순차힙, 최대힙)

[힙 생성]

1. 삽입식 >> 모든 키들이 미리 주어진 경우, 또는 키들이 차례로 주어지는 경우 적용 가능

2. 상향식 >> 모든 키들이 미리 주어진 경우만 적용 가능

 

 

1. 삽입식 힙 생성

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

int H[99]; // 힙 배열
int n = 0; // 힙의 크기

void upHeap(int i) {// ket 삽입 후 정렬하는 함수
	int tmp;
	if (i == 1)
		return;

	if (H[i] <= H[i / 2]) // i가 root가 아닐 때 부모노드보다 작으면 그대로 반환
		return;

	// i가 부모노드보다 크다면 swap해주기
	tmp = H[i];
	H[i] = H[i / 2];
	H[i / 2] = tmp;

	upHeap(i / 2);// 부모노드가 바꼈으니까 다시 호출해서 그 부모노드의 부모노드와 값 비교해주기
}

void downHeap(int i) {// 최대힙 반환 후 정렬하는 함수
	int left = i * 2; //왼쪽 자식노드 인덱스, i는 1로 호출됐기 때문에 root
	int right = i * 2 + 1; // 오른쪽 자식노드 인덱스
	int max, tmp; //max값
	if (n < left && n < right)// 자식노드가 둘다 없다면 반환
		return;

	max = left;// 아니라면 max에 왼쪽 자식노드 인덱스를 넣음
	if (n >= right) {// 오른쪽 자식노드도 있다면
		if (H[max] < H[right]) {//그리고 왼쪽 자식노드 값보다 오른쪽 자식노드 값이 크다면
			max = right;// max에 오른쪽 자식노드 인덱스를 저장
		}
	}

	if (H[max] <= H[i])// max에는 왼쪽 or 오른쪽 자식노드 인덱스가 들어있음, 그 값이 root값보다 적다면 그냥 반환
		return;
	// 아니라면 == 왼쪽 or 오른쪽 자식노드 값이 root값보다 크다면 swap
	tmp = H[i];
	H[i] = H[max];
	H[max] = tmp;

	downHeap(max);
}

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]);
	}
	printf("\n");
}

int main() {
	char type;
	int key;

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

	return 0;
}

 

 

2. 상향식 힙 생성

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

int H[99]; // 힙 배열
int n; // 힙의 크기

void downHeap(int i) {
	int left = i * 2;
	int right = i * 2 + 1;
	int max, tmp;
	if (n < left && n < right)
		return;

	max = left;
	if (n >= right) {
		if (H[max] < H[right]) {
			max = right;
		}
	}

	if (H[max] <= H[i])
		return;

	tmp = H[i];
	H[i] = H[max];
	H[max] = tmp;

	downHeap(max);
}

void rBuildHeap(int i) {
	if (i > n)
		return;
	rBuildHeap(i * 2);
	rBuildHeap(i * 2 + 1);
	downHeap(i);

	return;
}

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

int main() {
	int i;

	scanf("%d", &n);

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

	rBuildHeap(1);
	printHeap();

	return 0;
}