Problem A : 힙정렬2 (Heap_Sort)

Problem A : 힙정렬2 (Heap_Sort)

 

제한시간: 1000 ms    메모리제한: 64 MB

 

 

정올이는 정수 배열을 입력받아 빠르게 정렬하는 임무를 부여받았다.

어떤 방법으로 정렬할까 망설이던 정올이는 배열을 max_heap구조로 만들어서 정렬하기로 했다. 

그 과정은 다음과 같다.

우선 push_heap 함수를 만들어 놓고 한 개씩 입력을 받을 때마다 함수를 실행해서 

계속 max_heap의 구조가 유지되도록 하면서 입력을 모두 끝낸다.

그리고 입력이 제대로 진행되었는지 확인하기 위해 모든 자료를 출력한다.

 

예를 들어 입력 자료가 3 6 4 8 9 7 이렇게 6개라고 하면 입력받아서 처리하는 과정은 아래와 같고 출력을 하면 9 8 7 3 6 4가 된다. 

 

 

입력이 끝나면 pop_heap 함수를 만들어서 첫 번째와 마지막 자료를 바꾼후 pop_heap을 호출하여 

마지막 자료를 제외한 나머지가 max_heap의 구조가 유지되도록 하는 작업을 자료의 개수만큼 반복하여 정렬을 끝낸다. 

그리고 최종적으로 오름차순으로 정렬된 자료를 모두 출력한다.

 

정올이를 도와 위와같이 출력하는 프로그램을 작성해 주자.

첫 번째 줄에는 데이터의 개수 N이 입력된다. (1≤N≤500,000) 두 번째 줄에 N개의 숫자가 공백으로 구분되어 입력된다. (1≤N개의 입력데이터 ≤21억)

첫 번째 줄에는 입력을 받으면서 max_heap의 구조가 된 N개의 숫자를 차례로 출력한다. 두 번째 줄에는 힙정렬을 끝내고 오름차순으로 정렬된 자료를 차례로 출력한다.

 

6

3 6 4 8 9 7

 

9 8 7 3 6 4

3 4 6 7 8 9

 

#include <stdio.h>

#define MAX 7 // 500100

int N, hcnt, heap[MAX];

void Swap(int &x, int &y) { int z = x; x = y; y = z; }

void push(int p)
{
	if (p <= 1 || heap[p / 2] >= heap[p]) return; // 처음 요소 이거나, 부모가 더 크면(제자리에 있으면)
	Swap(heap[p / 2], heap[p]); // 부모와 자리를 바꿈
	push(p / 2); // 부모 노드에 대해 다시 재귀적으로 처리
}

void pop(int p)
{
	int np = p * 2;
	if (np > hcnt) return; // 제일 하단 노드이면
	if (np < hcnt && heap[np] < heap[np + 1]) np++; // 왼쪽과 오른쪽 비교 
	if (heap[p] >= heap[np]) return; // 본인이 자식보다 크면 그대로
	Swap(heap[p], heap[np]);
	pop(np); // 재귀적으로 제자리를 찾아각ㅁ
}

void output()
{
	for (int i = 1; i <= N; i++) printf("%d ", heap[i]); // 위에서 부터 하나씩 출력
	printf("\n");
}
int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	hcnt = N;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &heap[i]);
		push(i);
	}
	output();
	while (hcnt > 1) {
		Swap(heap[1], heap[hcnt--]);
		pop(1);
	}
	output();
	return 0;
}