[C] 백준 2750번: 수 정렬하기(힙 정렬)

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

typedef struct PriortyQueue {
	int* H;
	int length;
}PriortyQueue;

void printNumbers(int* nums, int length) {
	for (int i = 1; i < length+1; i++) printf("%d\n", nums[i]);
}

void swapNumbers(PriortyQueue* pqueue, int index1, int index2) {
	int tmp = pqueue->H[index1];
	pqueue->H[index1] = pqueue->H[index2];
	pqueue->H[index2] = tmp;
}

void doUpheap(PriortyQueue* pqueue, int index) {
	int parent = index / 2;
	if (index <= 1 || pqueue->H[parent] > pqueue->H[index]) return;

	swapNumbers(pqueue, index, parent);
	doUpheap(pqueue, parent);
}

int getGreaterChildIndex(PriortyQueue* pqueue, int index) {
	int res = index * 2;
	if (res > pqueue->length-1) return -1;

	if (res+1 <= pqueue->length-1 && pqueue->H[res] < pqueue->H[res+1]) res += 1;

	return res;
}

void doDownheap(PriortyQueue* pqueue, int index) {
	int child = getGreaterChildIndex(pqueue, index);
	if (child == -1 || pqueue->H[index] > pqueue->H[child]) return;

	swapNumbers(pqueue, index, child);
	doDownheap(pqueue, child);
}

void doHeapSort(PriortyQueue* pqueue) {
	int i;
	// 1기
	for (i = 2; i < pqueue->length; i++)
		doUpheap(pqueue, i);

	// 2기
	for (i = pqueue->length-1; i >= 2; i--) {
		swapNumbers(pqueue, 1, i);
		pqueue->length -= 1;
		doDownheap(pqueue, 1);
	}
}

int main() {
	// Input
	int N;
	scanf("%d", &N);

	PriortyQueue* pqueue = (PriortyQueue*) malloc(sizeof(PriortyQueue));
	pqueue->H = malloc(sizeof(int) * (N+1));
	pqueue->length = N+1;
	for (int i = 1; i < N+1; i++)
		scanf("%d", &pqueue->H[i]);

	// Solution
	doHeapSort(pqueue);
	printNumbers(pqueue->H, N);

	// Free
	free(pqueue->H);
	free(pqueue);

	return 0;
}

 

배열을 [우선순위큐 / 일반 원소]로 나누며 phase가 2개로 나뉜다.

첫번째 phase에서는 기존 원소의 앞쪽부터 순차적으로 우선순위큐에 삽입을 해준다. 삽입은, 우선순위큐의 마지막 원소에 넣고 이것을 upheap 해줌으로써 진행된다. 결과적으로 MaxHeap이 구성되게끔 설계한다.

두번째 phase에서는 우선순위큐에서 max를 1개씩 꺼내주면서 정렬된 배열을 뒤부터 완성시켜나간다. max를 꺼낸 뒤에, max와 swap을 당한 원소를 downheap 해줌으로써 줄어드는 우선순위큐을 유지해준다.

 

시간 복잡도: O(NlogN), logN의 작업(downheap, upheap)을 2N번 해주기 때문이다.

공간 복잡도: O(1)

안정성: 불안정, 우선순위큐를 사용하기 때문이다.