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

[제자리 힙 정렬]

- 힙 생성 방식은 삽입식, 상향식 중 아무거나 사용

- 순차힙을 통해 구현한다면 추가 메모리를 사용하지 않고 제자리 힙 정렬이 가능함

- 유일키

- 중복키

- 중복 키를 처리할 수 있도록 작성된 알고리즘은 유일 키 환경에서도 정확히 작동한다. 하지만 유일 키를 처리할 수 있도록 작성된 알고리즘은 중복 키 환경에서도 정확히 작동한다는 보장은 없음 >> 유일키 알고리즘에 = (등호) 경우를 빼지않았다면 중복키 환경에서도 작동할 것이라고 교수님이 강의 중 언급하심

 

아래 코드는 상향식으로 힙을 생성하고 재귀함수를 이용해서 제자리 힙 정렬을 하는 알고리즘이다.

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

int H[99];// 힙
int n;// 키 개수(힙의 크기)
int s;// 힙의 원래 크기 저장할 변수

void downHeap(int i) {
	int left = i * 2;//왼쪽 자식
	int right = i * 2 + 1;//오른쪽 자식
	int big, tmp;
	if (n < left && n < right)
		return;

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

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

	tmp = H[i];
	H[i] = H[big];
	H[big] = tmp;

	downHeap(big);
}

void rBuildHeap(int i) { // 상향식 힙 생성 함수
	if (i > n)
		return;
	rBuildHeap(i * 2);
	rBuildHeap(i * 2 + 1);
	downHeap(i);

	return;
}

void inPlaceHeapSort() { // 제자리 힙 정렬 함수
	int tmp;
	s = n;

	for (int i = n; i >= 2; i--) {
		tmp = H[1];
		H[1] = H[i];
		H[i] = tmp;
		n--;

		downHeap(1);
	}
}

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


int main() {
	
	scanf("%d", &n);

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

	rBuildHeap(1);

	inPlaceHeapSort();
	printArray();
	
	return 0;
}