Heap Sort

힙 정렬은 말 그대로 힙이라는 자료구조를 이용하여 정렬하는 것을 말한다.

Heap

힙은 최댓값 및 최솟값을 빠르게 찾기 위해 고안된 완전이진트리를 기반으로 하는 자료구조이다.
완전이진트리의 조건
1. 마지막 높이를 제외한 나머지 높이에서는 빈 노드가 존재하지 않는다.
2. 마지막 높이에서는 왼쪽의 자식 노드부터 채워져 있어야 한다.
3. 다시 말해, 노드를 삽입하는 순서는 왼쪽, 오른쪽을 반복한다.
완전이진트리의 조건에 따라 트리를 직접 구현하지 않아도 배열을 이용하여 완전이진트리를 구현할 수 있다.
힙 정렬은 이진 힙을 기반으로 하는 최대 힙, 최소 힙을 이용한다.
이진 힙의 조건은 최대 힙일 경우, 모든 레벨에서 부모 노드의 값이 자식 노드의 값보다 커야 하고, 최소 힙일 경우, 모든 레벨에서 부모 노드의 값이 자식 노드의 값보다 작아야 한다.

int pq[135001];

void sw(int &a, int &b) {
	int t = a;
	a = b;
	b = t;
}

void pq_push(int num) {
	if (s > 135000) return;
	pq[++s] = num;
	for (int i = s; i > 1 && pq[i] < pq[i / 2]; i /= 2) sw(pq[i], pq[i / 2]);
}

int pq_pop() {
	int r = pq[1];
	pq[1] = pq[s--];
	int i = 1;
	while (1) {
		if (i * 2 + 1 <= s) {
			int next = pq[i * 2] < pq[i * 2 + 1] ? i * 2 : i * 2 + 1;
			if (pq[next] < pq[i]) sw(pq[i], pq[next]), i = next;
			else break;
		}
		else if (i * 2 <= s) {
			if (pq[i * 2] < pq[i]) sw(pq[i], pq[i * 2]), i *= 2;
			else break;
		}
		else break;
	}
	return r;
}

위와 같이 삽입 식으로 힙을 구현해도 되지만, 존재하는 배열을 바로 Heap으로 변환하면, 시간을 단축할 수 있다. (O(NlogN) -> O(N))