11. 힙 정렬(Heap Sort)

힙 정렬은 빠른 알고리즘을 가지고 있다.

힙 정렬은 이진트리구조를 사용한다.

이진트리 구조(자식 노드가 2개 이하인 트리 구조)

 

완전 이진 트리는 루트부터 자식노드가 왼쪽부터 오른쪽으로 차례대로 데이터가 들어가는 구조이다.

 

힙 생성 알고리즘은 특정 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다.

위치를 바꾼 뒤에도 자식이 존재하는 경우 계속해서 반복한다.

이 힙 생성 알고리즘의 시간복잡도는 높이와 같기 때문에 O(log N) 이다.

 

 

 

 

<샹향식 힙구조 만드는 법>

1. 배열에 그대로 삽입한다.

2. 앞의 1/2개만 확인한다.(소수점은 버림) 위의 그림에서는 7, 6, 5, 8까지만 본다.

3. 밑에서부터 자식과 확인하며 정렬한다.

 1) 8은 1, 6보다 크므로 그대로

 2) 5는 9보다 작으므로 9와 자리 바꿈. 해당 9는 위의 7보다 또 크므로 7과 자리 바꿈

 3) 6은 ...

 

 

4. root에 있는 값을 가장 밑에 있는 값과 자리를 바꾼다.

실행 결과(상단)은 9에 대해 힙 정렬이 되었으므로 9를 가장 밑에 있는 6과 자리바꿈(하단).

 

5. 그 다음 정렬된 9를 제외한 나머지를 같은 방식으로 반복하여 정렬.

 

이렇게 힙 정렬의  전체 시간복잡도는

힙 생성 알고리즘의 시간 복잡도 O(log N) x 전체 데이터의 갯수 N

= O(N * log N) 가 된다.

 

힙 정렬은 병합 정렬과 다르게 별도로 추가적인 배열이 필요하지 않다는 점에서 메모리 측면에서 몹시 효율적이고 항상 O(N * log N)을 보장할 수 있다.

#include <stdio.h>

int number = 9;
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};

int main(void) {
	// 힙을 구성 
	for(int i = 1; i < number; i++) {
		int c = i;
		do {
			int root = (c - 1) / 2;
            //root부모가 c자식보다 작으면 위치 바꿈.
			if(heap[root] < heap[c]) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
            //부모를 자식에 두고 재귀하여 반복
			c = root;
		} while (c != 0);
	}
	// 크기를 줄여가며 반복적으로 힙을 구성
	for (int i = number - 1; i >= 0; i--) { 
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int c = 1;
		do {
			c = 2 * root + 1;
			// 자식 중에 더 큰 값을 찾기 
			if(c < i - 1 && heap[c] < heap[c + 1]) {
				c++;
			}
			// 루트보다 자식이 크다면 교환 
			if(c < i && heap[root] < heap[c]) {
				temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			root = c;
		} while (c < i);
	} 
	// 결과 출력 
	for(int i = 0; i < number; i++) {
		printf("%d ", heap[i]);
	}
}

 

출력 결과

 

< 하향식 구현 방식>

 

10 26 5 37 1 61 11 59 15 48 19

​

위와 같이 10개의 원소가 들어왔을 때 다음과 같은 정렬 과정이 출력되도록 하는 프로그램을 작성하세요. 이 때 힙 생성을 함에 있어서 하향식으로 구현을 하셔야 정상적으로 답이 출력됩니다.

​

< 예시 출력 >

61 48 59 26 19 11 37 15 1 5

59 48 37 26 19 11 5 15 1 61

48 26 37 15 19 11 5 1 59 61

37 26 11 15 19 1 5 48 59 61

26 19 11 15 5 1 37 48 59 61

19 15 11 1 5 26 37 48 59 61

15 5 11 1 19 26 37 48 59 61

11 5 1 15 19 26 37 48 59 61

5 1 11 15 19 26 37 48 59 61

1 5 11 15 19 26 37 48 59 61

​

<소스코드>

#include <iostream>
#include <vector>

using namespace std;

int number;
int heap[1000001];

void heapify(int i) {
	// 왼쪽 자식 노드를 가리킵니다. 
	int c = 2 * i + 1;
	// 오른쪽 자식 노드가 있고, 왼쪽 자식노드보다 크다면 
	if(c < number && heap[c] < heap[c + 1]) {
		c++;
	}
	// 부모보다 자식이 더 크다면 위치를 교환합니다. 
	if(heap[i] < heap[c]) {
		int temp = heap[i];
		heap[i] = heap[c];
		heap[c] = temp;
	} 
	// number / 2까지만 수행하면 됩니다. 
	if(c <= number / 2) heapify(c);
}

int main(void) {
	cin >> number;
	for(int i = 0; i < number; i++) {
		int x;
		cin >> heap[i];
	}
	// 힙을 생성합니다. 
	for(int i = number / 2; i >= 0; i--) {
		heapify(i);
	}
	// 정렬을 수행합니다. 
	for (int i = number - 1; i >= 0; i--) { 
		for(int j = 0; j < number; j++) {
			cout << heap[j] << ' ';
		}
		cout << '\n';
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int c = 1;
		do {
			c = 2 * root + 1;
			if(c < i - 1 && heap[c] < heap[c + 1]) c++;
			if(c < i && heap[root] < heap[c]) {
				temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			root = c;
		} while (c < i);
	}
}

 

 

출력 결과

10 26 5 37 1 61 11 59 15 48 19 입력 시