알고리즘 - Heap Sort (힙 소트(힙 정렬)를 구현하라)

| 문제

입력(표준 입력)

첫번째 줄에, 입력할 숫자들의 개수 N와 정수 k를 입력합니다.

다음줄 부터 N개의 줄만큼, 각각의 줄마다 하나의 입력 변수를 입력해야 합니다.

출력(표준 출력)

첫 번째 줄에는, 내림차순으로 가장 큰 k개의 원소들을 출력해 냅니다.

두 번째 줄에는, 가장 큰 k 원소들을 추출해낸 후에 힙을 출력해 냅니다.

 

ex) 

 

입력	출력
10 4 16 14 10 8 7 9 3 2 4 1	16 14 10 9 8 7 3 4 2 1

 

 | 소스 코드 

#include <stdio.h>

void array_swap(int * arr, int a, int b)
{
	int temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void Heapify(int * arr, int parent_position, int heap_size)
{
	int left, right, largest;
	left=2*parent_position+1;
	right=2*parent_position+2;

	if((left<heap_size)&&(arr[left]>arr[parent_position]))
		largest = left;
	else
		largest = parent_position;

	if((right<heap_size)&&(arr[right]>arr[largest]))
		largest = right;

	if(largest != parent_position)
	{
		array_swap(arr, parent_position, largest);
		Heapify(arr, largest, heap_size);
	}
}

void Build_Heap(int * arr, int length)
{
	int parent_position;

	for(parent_position=length/2-1; parent_position>=0; parent_position--)
		Heapify(arr, parent_position, length);
}

void Heap_Sort(int * arr, int length, int k)
{
	Build_Heap(arr, length);
	int last_row;
	int count = 0;

	for(last_row = length-1; last_row>0; last_row--)
	{
		if(count == k)
			break;
		array_swap(arr, 0, last_row);
		length--;
		count ++;

		Heapify(arr, 0, length);
	}
}
int main(void)
{
	int arr[100000];
	int length = 10;
	int N, k, i;

	// input
	scanf("%d %d", &N, &k);
	for(i=0; i<N; i++)
	{
		scanf("%d", &arr[i]);
	}
	Heap_Sort(arr, N, k);

	// output
	for(i=N-1; i>(N-1)-k; i--)
		printf("%d ", arr[i]);

	printf("\n");
	for(i=0; i<=(N-1)-k; i++)
		printf("%d ", arr[i]);

	printf("\n");

	return 0;
}