[ 정렬 - 24174 ] 알고리즘 수업 - 힙 정렬 2(C++)

문제

---

접근법

https://jinwoo-jung.tistory.com/56

[ 정렬 - 24173 ] 알고리즘 수업 - 힙 정렬 1(C++)

 

지난 힙 정렬 1에서 설명한 Heap과 해당 코드의 내용으로 접근법에 대한 설명한 생략한다.

 

이번 문제는 교환 횟수에 따라서, 해당 교환까지 진행한 전체 Tree의 정렬 상태를 출력하는 문제이다.

이전에 언급 한 것처럼, s32_N Index는 Sorting() 과정에서 줄어든다. 따라서 전체 트리의 길이를 처음에 받아올 때, 전역변수로 하여 s32_Num에 저장한 후, 특정 교환이 진행 시 1부터 s32_Num까지 for문을 돌면서 전체 Tree의 정렬 상태를 출력하도록 하였다. 

 

힙 정렬 1을 완벽히 이해했다면,,어렵지 않을 것이다.

---

정답

#include<iostream>
using namespace std;

void heapify(int32_t ars32_A[], int32_t s32_K, int32_t s32_N);
void heapsort(int32_t ars32_A[], int32_t s32_N);
void build_mean_heap(int32_t ars32_A[], int32_t s32_N);

int32_t s32_Cnt = 0, s32_Kmax, s32_Num, ars32_A[500001];
bool flag = true;

int main()
{
	int32_t s32_I;
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> s32_Num >> s32_Kmax;

	for (s32_I = 1; s32_I <= s32_Num; s32_I++)
	{
		cin >> ars32_A[s32_I];
	}

	heapsort(ars32_A, s32_Num);

	if (s32_Cnt < s32_Kmax)
	{
		cout << -1;
	}
	return 0;
}

void build_mean_heap(int32_t ars32_A[], int32_t s32_N)
{
	int32_t s32_I;

	for (s32_I = s32_N / 2; s32_I > 0; s32_I--)
	{
		heapify(ars32_A, s32_I, s32_N);
	}
}

void heapsort(int32_t ars32_A[], int32_t s32_N)
{
	int32_t s32_I;

	build_mean_heap(ars32_A, s32_N);

	for (s32_I = s32_N ; s32_I > 1; s32_I--)
	{
		if (flag)
		{
			int32_t s32_Tmp = ars32_A[1];
			ars32_A[1] = ars32_A[s32_I];
			ars32_A[s32_I] = s32_Tmp;
			s32_Cnt += 1;

			if (s32_Cnt == s32_Kmax)
			{
				for (s32_I = 1; s32_I <= s32_Num; s32_I++)
				{
					cout << ars32_A[s32_I] << " ";
				}
				cout << endl;
				return;
			}
			heapify(ars32_A, 1, s32_I - 1);
		}
		else
			return;
	}
}

void heapify(int32_t ars32_A[], int32_t s32_K, int32_t s32_N)
{
	int32_t s32_Left = s32_K * 2;
	int32_t s32_Right = s32_K * 2 + 1;
	int32_t s32_Smaller;

	if (s32_Right <= s32_N)
	{
		if (ars32_A[s32_Left] < ars32_A[s32_Right])
		{
			s32_Smaller = s32_Left;
		}
		else
		{
			s32_Smaller = s32_Right;
		}
	}
	else if (s32_Left <= s32_N)
	{
		s32_Smaller = s32_Left;
	}
	else
		return;

	if (ars32_A[s32_Smaller] < ars32_A[s32_K])
	{
		int32_t s32_I;

		int32_t s32_Tmp = ars32_A[s32_Smaller];
		ars32_A[s32_Smaller] = ars32_A[s32_K];
		ars32_A[s32_K] = s32_Tmp;
		s32_Cnt += 1;

		if (s32_Cnt == s32_Kmax)
		{
			for (s32_I = 1; s32_I <= s32_Num; s32_I++)
			{
				cout << ars32_A[s32_I] << " ";
			}
			cout << endl;
			flag = false;
			return;
		}
		heapify(ars32_A, s32_Smaller, s32_N);
	}
}