[백준 2750번][C++] 수 정렬하기 - 4. 힙 정렬

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

void MakeMaxHeap(vector<int>& v)
{
	// 최대힙을 생성하는 함수
	// 완전이진트리의 노드번호는 1번부터 시작하기때문에 0번 인덱스를 1번으로 취급해야함
	// 0번을 시작으로할때
	// 자식노드번호가 홀수인 경우, 부모인덱스 = 자식 인덱스 / 2
	// 자식노드번호가 짝수인 경우, 부모인덱스 = 자식 인덱스 / 2 - 1
	for (int i = 1; i < v.size(); i++) // 0번은 부모가 없으므로 1번부터 시작
	{
		// Root가 아닐때까지 반복 -> 가장 큰 수라면 밑 부터 차례대로 바꿔가면서 Root까지 올라감
		while (i > 0)
		{
			int ParentIndex;

			if (i % 2 != 0)
			{
				// 홀수
				ParentIndex = i / 2;
			}
			else
			{
				// 짝수
				ParentIndex = i / 2 - 1;
			}
			
			// 부모보다 자식의 값이 더 큰 경우 -> swap
			if (v[i] > v[ParentIndex])
			{
				swap(v[i], v[ParentIndex]); // 값 변경
				i = ParentIndex; // 실제 인덱스도 변경 
			}
			else break;
		}
	}
}

void Heapify(vector<int>& v, int curRoot, int range)
{
	// 다시 제자리로 찾아가게 만드는 함수
	int curIndex = curRoot; // 현재 index(부모)
	int leftchild = curRoot * 2 + 1; // 왼쪽 자식
	int rightchild = curRoot * 2 + 2; // 오른쪽 자식

	// 왼쪽 자식과 비교
	if (leftchild <= range && v[leftchild] > v[curIndex])
	{
		curIndex = leftchild;
	}

	//오른쪽 자식과 비교
	if (rightchild <= range && v[rightchild] > v[curIndex])
	{
		curIndex = rightchild;
	}

	// 바뀐 경우
	if (curIndex != curRoot)
	{
		swap(v[curIndex], v[curRoot]); // 왼쪽과 오른쪽 중 더 큰 값과 교환

		Heapify(v, curIndex, range); // 재귀 호출
	}
}

void HeapSort(vector<int>& v)
{
	MakeMaxHeap(v); // 최대힙 생성

	for (int i = v.size() - 1; i >= 1; i--)
	{
		swap(v[i], v[0]); // root와 정렬이 안된 마지막 노드 교환

		Heapify(v, 0, i - 1);
	}
}

int main()
{	
	int N; 
	cin >> N;

	vector<int> v;

	// 원소 입력
	while (N > 0)
	{
		int x;
		cin >> x;

		v.push_back(x);
		N--;
	}

	// 4. 힙 정렬
	// 인덱스 번호를 이용해 완전이진트리 꼴로 생각하고 계산
	// 왼쪽 자식의 노드 번호 = 부모 노드 번호 x 2, 오른쪽 자식의 노드 번호 = 부모 노드 번호 x 2 + 1 
	// 왼쪽, 오른쪽 자식 노드 번호 / 2 = 부모 노드 번호

	// 원래는 이 방법으로 구해야해서 0번 인덱스를 비워놓아야하는데 우리는 그럴 수 없어서 식을 조금 변형하였다.
	// 홀수 자식의 노드번호 = 부모 노드번호 * 2 + 1
	// 짝수 자식의 노드번호 = 부모 노드번호 * 2 + 2
	// 홀수 자식의 부모 노드번호 = 자식 노드번호 / 2
	// 짝수 자식의 부모 노드번호 = 자식 노드번호 / 2 - 1
	
	// 정렬 방법
	// 1. 힙을 만든다
	// - 최대힙 : 부모 노드의 값이 자식 노드의 값보다 큰 완전이진트리 꼴 -> 오름차순 정렬에 사용
	// - 최소힙 : 부모 노드의 값이 자식 노드의 값보다 작은 완전이진트리 꼴 -> 내림차순 정렬에 사용
	// 2. root node와 가장 마지막 node의 값을 swap
	// 3. root node에 있는 값은 다시 제자리로 보냄 -> 이떄 순차적으로 N-1, N-2 ... Node 까지만 비교

	HeapSort(v);

	// 원소 출력
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}

	return 0;
}

---

<풀이과정>

1. 최대힙을 생성 (MakeMaxHeap)

1-1. 가장 큰 수를 Root 노드로 만드는 과정이다.

1-2. 이때 원래는 완전이진트리의 특성을 이용해 0번 인덱스는 비워두고 1번 인덱스로 시작해야하지만 문제 특성상 그럴 수 없어서 공식을 조금 수정했다.

1-3. 자식 노드가 홀수인 경우, 부모 인덱스 = 자식 인덱스 / 2

1-4. 자식 노드가 짝수인 경우, 부모 인덱스 = 자식 인덱스 / 2 - 1

1-5. 이를 이용해서 원래 Root 노드인 0번 인덱스를 제외한 1번 인덱스부터 차례로 Root 노드와 비교한다.

1-6. 만약 Root 노드보다 큰 수라면 Root  노드와 swap해주고 다음 인덱스를 진행한다.

1-7. 만약 Root 노드보다 작은 수라면 그냥 다음 인덱스로 넘어가 진행한다.

1-8. 이 과정을 반복하면 가장 큰 수가 Root 노드가 되는 최대힙이 완성된다.

 

2. 최대힙을 이용해 각 원소를 오름차순 순서로 정렬함(Heapify)

2-1. 먼저 Heapify() 함수는 인자로 Root 노드와 정렬할 범위를 받는다. (curRoot, range)

2-2. 완전이진트리의 특성을 이용해 좌우측 노드의 인덱스 번호를 구한다.(변형시킨 공식 이용)

2-3. 왼쪽 자식 인덱스(leftchild) = 부모 인덱스 * 2 + 1(원래는 +0)

2-4. 오른쪽 자식 인덱스(rightchild) = 부모 인덱스 * 2 + 2(원래는 +1)

2-5. curRoot의 갑도 현재 노드의 인덱스라는 변수 curIndex에 복사 생성 해준다. 

2-6. curIndex의 값과, leftchild, rightchild의 값을 비교하여 가장 큰 값을 가지는 노드와 curIndex의 노드 값을 swap 해준다.

2-7. curIndex의 값이 바뀌지 않았다면 함수를 종료시키고, curIndex의 값이 변경된 경우 변경된 curIndex를 curRoot로 하는(이때 curRoot의 값은 변경되지만, v[curRoot]의 값은 변경되지 않는다.) 같은 range 내의 Heapify() 함수를 재귀적으로 호출해서 결과적으로 range내의 가장 큰 노드는 Root 노드의 위치에 있게되고, curRoot는 오름차순 정렬했을 때의 인덱스로 위치하게 된다.

 

3. 벡터 v의 마지막 원소부터 반복문을 돌면서 반복을 진행한다.

4. 먼저, 최대힙으로 만든 벡터의 맨 마지막 원소와 Root 원소를 swap해준다.

5. 그러면 가장 큰 수가 맨 마지막에 위치한 것이므로 해당 수를 제외한 범위에서 Heapify를 이용해 다음으로 가장 큰 수를 Root 노드로 만들고, 다음 반복시에 다시 4번 과정을 함으로써 해당 수를 오름차순 정렬했을 때의 인덱스로 위치시킨다.

6. 1번 인덱스까지 이 과정을 반복하면서 오름차순 정렬을 완성한다.

---

<코멘트>

이번엔 네번째 방법인 힙 정렬로 풀어보았다!

이해하기 어렵쓰였다..ㅋㅋㅋ

완전이진트리는 1번 노드부터 시작해서 원래는 배열의 첫 인덱스인 0번 인덱스를 비우고 시작하는데 이 문제 특성상 그러기가 힘들 것 같아서 따로 공식을 생각해서 조금 다르게 구현했다.

 

- 힙 정렬 -

장점 

- 추가적인 메모리를 필요로 하지 않으면서 항상 O(nlogn)이라는 시간복잡도를 가지는 굉장히 효율적인 정렬법이라고 볼 수 있다.

- 가장 큰 값이나 가장 작은 값을 구할 때 유용하다.

 

단점

- 이상적인 경우에 퀵 정렬과 비교했을 때 똑같이 O(nlogn)이 나오긴 하지만 실제 시간을 측정해보면 퀵 정렬보다 느리다.

- 즉, 데이터의 상태에 따라서 다른 정렬법들에 비해 조금 느린 편이다. (캐시 친화도가 떨어짐, 포인터 연산 사용에 따른 무시할 수 없는 수준의 오버헤드)

- 안정성을 보장받지 못한다.

 

특징 

1. 시간복잡도

- 최악 : O(nlogn)

- 평균 : O(nlogn)

2. 공간복잡도 O(n)

3. in-place정렬 - 주어진 배열 내에서만 위치를 바꾸기 때문

4. not-stable정렬 

 

<cf>

1. stable vs not-stable

- stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻함.

- 즉 , 정렬했을 때 중복된 키 값이 원래 순서대로 정렬되어있으면 stable 아니면 not-stable이다.

2. in-place vs not in-place

- in- place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻함.

- not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻함.

---

<제출 결과>

<힙 정렬> - 퀵 정렬보다 느린 시간대

<퀵 정렬> - 준수한 시간이라 선택정렬과 비슷한 시간대가 나온듯..?

<비교 - 선택정렬> - 버블정렬에 비해 조금 더 빠르다는 것을 알 수 있음

<비교 - 버블정렬> 

 

---