[알고리즘] 힙정렬 (Heap Sort) - C/C++

힙정렬 (Heap Sort)

1. 기본동작

1) 모든 노드를 순회하면서, 현재 노드를 기준으로 위쪽으로 올라가며 Heapify 한다.

2) 루트 값을 가장 뒤쪽으로 보내고 Heapify 하며 크기를 줄여간다.

 

2. 시간복잡도 : O(N * log N)

 

3. 구현

- BOJ 의 11650번 좌표정렬하기를 힙정렬을 직접 구현하여 풀었습니다. (www.acmicpc.net/problem/11650)

- 아래 heapSort 코드는 SWEA(swexpertacademy.com/main/visualcode/main.do#/home/mainlayout) 에서

Priority Queue의 레퍼런스 코드를 참고하여 구현하였습니다.

 

#include <stdio.h>

struct Node {
	int x, y;
} heap[100001];
int N;

bool isBigger(int a, int b) {
	return (heap[a].x > heap[b].x) || ((heap[a].x == heap[b].x) && (heap[a].y > heap[b].y));
}

void heapSort()
{
	// 모든 노드를 순회하면서, 현재 노드를 기준으로 위쪽으로 올라가며 Heapify
	for (int i = 1; i < N; i++) {
		int current = i;
		while (current > 0 && isBigger(current, (current - 1) / 2))	{
			Node temp = heap[(current - 1) / 2];
			heap[(current - 1) / 2] = heap[current];
			heap[current] = temp;
			current = (current - 1) / 2;
		}
	}

	// 크기 줄여가며 정렬
	for (int i = N - 1; i >= 0; --i) {
		Node temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;

		int current = 0;
		while (current * 2 + 1 < i)
		{
			int child;
			if (current * 2 + 2 == i) child = current * 2 + 1;
			else child = isBigger(current * 2 + 1, current * 2 + 2) ? current * 2 + 1 : current * 2 + 2;

			if (isBigger(current, child)) {
				break;
			}

			Node temp = heap[current];
			heap[current] = heap[child];
			heap[child] = temp;
			current = child;
		}
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d %d", &heap[i].x, &heap[i].y);

	heapSort();

	for (int i = 0; i < N; ++i) printf("%d %d\n", heap[i].x, heap[i].y);
}

 

GitHub

geonhee7721/PS-Backjoon