3주차 자료구조 스터디 - 힙정렬(Heap sort)

3주차 이번 주 주제는 <정렬> 이었다.

힙정렬에 대해서 공부하기전에 힙에 대해 알아야 한다. 

0) 힙이란 ?

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)

•  부모노드와 자식노드 사이에 일정한 대소관계가 존재한다. 
•  부모노드가 자식노드보다 더 크면 최대힙(max heap) 
•  부모노드가 자식노드보다 더 작으면 최소힙(min heap)
•  형제끼리는 대소관계가 존재하지 않는다.
•  부모와 자식간의 인덱스는 왼쪽자식 = 2 * 부모노드 , 오른쪽 자식 = 2 * 부모노드 +1 을 성립한다.

그림으로 보는 게 훨씬 직관적이다. 

부모노드가 자식노드보다 큰 최대힙의 경우이다. 형제끼리는 대소관계가 없다.

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

1 ) 힙정렬이란?

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법

• 오름차순을 구성하고싶으면 최소 힙트리 

• 내림차순을 구성하고싶으면 최대 힙트리 

• 힙정렬을 사용하기 위해서는 들어온 배열을 우선 힙으로 만들어주어야한다.

2) 힙정렬 원리

* 트리의 아래로 내려갈수록 수가 커지는 오름차순으로 얘기해보자. 

1. arr[1] ~ arr[n] 을 힙으로 만든다. 

  1-1. 부모노드의 인덱스를 n / 2 부터 1까지 내려가면서 자식노드와 비교한다. 

  1-2. 만일 자식노드 중 하나가 부모노드보다 크다면 자식노드와 부모노드의 값을 비교한다.

  1-3. 자식노드가 모두 부모노드보다 작다면 넘어간다.  

  1-4. 뒤바뀐 자식노드를 부모노드로 설정하고 1을 반복한다.   

2. arr[1]과 arr[n]을 바꾼다.

3. arr[n]을 제외하고 arr[1] ~ arr[n-1]에 대해서 1~2번을 반복한다. 

 

이런식으로 n을 하나씩 줄이며 1~3 과정을 반복하면 된다. 

사실 나도 처음에는 이해가 잘 안되었다. 그림을 보며 이해하는 게 훨씬 이해가 잘 된다.  

 

3) 힙정렬 시간복잡도 : nlogn

• 힙을 구성하는 데 드는 시간 : log n

• 힙을 정렬하는데 드는 시간 : n

* 삽입정렬, 버블정렬들에 비해 훨씬 빠르다.

4) 힙정렬 구현코드 C++

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int>arr;


void heap_tree(int idx , int size) {
	//왼쪽자식은 부모노드의 2배 , 오른쪽 자식은 부모노드의 2배+1
	int left = 2 * idx, right = 2 * idx + 1, temp = idx;

	//최종적으로 왼쪽 자식값보다 오른쪽 자식값이 더 크도록 정렬이 되어야합니다. 
	//그렇기때문에 왼쪽을 먼저 보고 오른쪽을 봐줍니다. 
	if (left <= size && arr[left] > arr[temp]) //범위 내에서 왼쪽자식 값이 부모값보다 크다면 
		temp = left;

	if (right<= size && arr[right] > arr[temp]) //범위 내에서 오른쪽 자식 값이 부모값보다 크다면 
		temp = right;

	if (temp != idx) {//temp값이 left, right로 바뀜 즉 자식 중 하나 이상이 부모보다 컸다.{
		swap(arr[idx], arr[temp]); // 둘의 위치를 바꿉니다. 
		return heap_tree(temp, size); //  그 후 재귀를 통해 바뀐 값을 부모로 하는 트리를 탐색해줍니다. 
	}//예를 들어 부모와 오른쪽 자식이 바꼈다면 바뀐 오른쪽 값 (원래 부모값)을 부모노드로 하는 아래 트리를 탐색
	return;
}

void heap_sort() {
	//heap_tree 를 통해서 제일 큰 값이 루트노드에 위치하게 됩니다. 
	//heap_sort를 통해서 제일 큰 값을 제일 마지막 말단 노드로 위치를 변경한 후 이 값을 제외하고 나머지 값들을 정렬합니다.
	for (int i = n; i > 1; i--) {
		swap(arr[i], arr[1]); // 루트에 위치한 제일 큰 값을 제일 말단으로 위치 이동
		heap_tree(1, i-1); // 말단 노드를 제외하고 맨 처음부터 다시 정렬 시행
	}
}

int main()
{
	scanf("%d", &n);
	arr.resize(n + 1);
	arr[0] = 0; //인덱스를 맞추기 위해 1부터 시작
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}

	// 맨 처음 힙으로 만들어주기 
	// 부모노드가 자식노드보다 더 크도록 
	for (int i = n / 2; i > 0 ; i--) {
		heap_tree(i, n);
	}

	//힙정렬 실시 
	heap_sort();
	
	// 출력 
	for (int i = 1; i <= n; i++) printf("%d\n", arr[i]);
}