[알고리즘] 힙정렬(HeapSort)

[ Heap 개념복습 ]

Heap은 일단 완전이진트리 이다.
하지만 다음과 같은 조건을 모두 만족시켜야한다.

1. 완전이진트리
2. 부모가 자식보다 우선순위가 높다.

(수직관계 / 상하관계로만 판단한다!)
( 우선순위에 대한 조건이 있어야만 하는게
힙은 우선순위 큐를 위해 나왔던 존재이기 때문이다! )

그리고 이런 Heap을 구현하기 위해
우리는 배열을 사용했다. 노드 대신.
( 배열을 사용한 이유는 전 포스트 참고 )

 

---

[ Heapify 알고리즘 ]

완전 이진 트리를 힙(Heap) 으로 구현하기 위해서,
힙 속성을 가지게 하는 알고리즘 기법

원소들을 하나하나씩 검사하여
힙 속성에 맞지 않을 경우
그 노드가 맞는 위치를 찾을 때까지 재배치시킨다.

 

---

[ HeapSort 구현방법 ]

힙정렬을 구현할 수 있는 방법은 많다.

1. HInsert HDelete 를 통해 기존 배열을 사용하지 않고
새 배열을 통해 힙구조를 만들어 나가는 방법
=> 추가되는 노드는 항상 맨끝 노드에 저장하여
우선순위를 판단하여 위로 끌어올려주는 방법

 

[ HInsert ]

 

저장할때 이렇게 맨 마지막에 붙여주고
GetParentIDX를 통해 부모값과 비교하여
자기 자리를 찾아주는 방법

 

[ HDelete ]

 

맨 위에꺼를 맨 마지막꺼와 바꿔주고
( 맨 위에꺼 추출의 의미 )
맨 위에꺼의 자리를 다시 찾아주는 방법
( 새로운 힙으로 만들어주는 방법 )



2. Heapify를 통해 기존 배열을 Heap 구조로 바꾸는 방법
=> 기존 배열 자체를 완전이진트리라고 보고
맨 위 노드부터 맨 끝 노드까지 차례대로
Heapify를 통해 Heap으로 만들어주는 방법

즉, 위에서부터 아래방향으로

작은범위에서 큰 범위로 힙을 키워나가는 것임.

여기서는 Heapify로 힙정렬을 구현하였다.
( HInsert를 이용하는 힙정렬은
"우선순위 큐" 포스트를 통해 구현할 수 있다 )

 

---

[ 기본 함수 ]

void Swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

int GetParentIDX(int idx) {
	return idx / 2;
}

 

---

[ 힙정렬함수 ]

void Heapify(int arr[], int idx, int len) {
	int parentIDX;
	while (parentIDX = GetParentIDX(idx)) {
		if (arr[idx] < arr[parentIDX]) break;
		else {
			Swap(arr, idx, parentIDX);
			idx = parentIDX;
		}
	}
}

이 Heapify 함수는 위쪽부터 아래쪽까지
차례대로 각 원소마다 힙정렬을 해준다.

이 함수는 재귀로 구현할 수 도 있지만
여기서는 while을 이용한 방법을 보였다.

만약 parentIDX == 0
즉, 현재 idx가 1번 루트노드라면
빠져나오는 방식이다.

 

---

[ main함수 ]

int main() {
	int arr[SIZE] = { 0,4,1,2,8,7,3,5,9,6,10 };
	int len = 10;

	// 각 데이터마다 힙정렬 해주기
	for (int i = 1; i<=len; i++) Heapify(arr, i, len);

	// 힙정렬 후 출력
	for (int i = 1; i <= len; i++) printf("%d ", arr[i]); 
	return 0;
}

여기서 arr[0]을 0으로 한 것은
트리의 idx가 1번부터 시작하는게 훨씬 편하기 때문이다.
따라서 Heapify 함수도 arr에서 idx가 1일때부터 시작되게 하였다.

다음 포스팅에서는 시간복잡도를 계산해볼 것이다.

 

---

[ 우선순위 큐 함수를 이용한 힙정렬 ]

 

이건 그 전 포스트에서 사용한 함수들 HInsert 와 HDelete를 바탕으로 만든 힙정렬이다.

 

void HeapInit(Heap* ph, PriorityComp pc) {
	ph->numOfData = 0;
	ph->comp = pc;
}

int HIsEmpty(Heap* ph) {
	return ph->numOfData == 0 ? 1 : 0;
}

int GetParentIDX(int idx) { return idx / 2; }
int GetLChildIDX(int idx) { return idx * 2; }
int GetRChildIDX(int idx) { return idx * 2 + 1; }

int GetHiPriChildIDX(Heap* ph, int idx) {
	// 자식이 없으면
	if (GetLChildIDX(idx) > ph->numOfData) return 0;
	// 마지막 자식이면
	else if (GetLChildIDX(idx) == ph->numOfData) return GetLChildIDX(idx);
	// 자식이 둘이면
	else {
		if ((*ph->comp)(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) > 0) return GetLChildIDX(idx);
		else return GetRChildIDX(idx);
	}
}

 

void HInsert(Heap* ph, HData data) {
	int idx = ph->numOfData + 1;

	while (idx != 1) {
		// data가 부모보다 우선이면 
		if ((*(ph->comp))(data,ph->heapArr[GetParentIDX(idx)]) > 0) {
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else {
			break;
		}
	}
	ph->heapArr[idx] = data;
	ph->numOfData += 1;
}

 

HData HDelete(Heap* ph) {
	HData retdata = ph->heapArr[1];
	HData lastdata = ph->heapArr[ph->numOfData];

	int parentIdx = 1;
	int childIdx;

	while (childIdx = GetHiPriChildIDX(ph, parentIdx)) {
		// 자식이 더 우선이면
		if ((*ph->comp)(ph->heapArr[childIdx], lastdata) >= 0) {
			ph->heapArr[parentIdx] = ph->heapArr[childIdx];
			parentIdx = childIdx;
		}
		else {
			break;
		}
	}
	ph->heapArr[parentIdx] = lastdata;
	ph->numOfData--;
	return retdata;
}

 

void HeapSort(int arr[], int n, PriorityComp pc) {
	Heap heap;
	HeapInit(&heap,pc);

	for (int i = 0; i < n; i++) {
		HInsert(&heap, arr[i]);
	}

	for (int i = 0; i < n; i++) {
		arr[i] = HDelete(&heap);
	}
}

 

int main() {
	int arr[6] = { 4,2,1,7,3,5};
	HeapSort(arr, 6, DataPriorityComp);

	for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
	return 0;
}