2075. N번째 큰 수

힙을 사용하면 금방 성공할 거 같았는데 진짜 많은 오류에 직면한 문제이다.

처음에는 N개의 노드를 가진 최소힙을 만들어서 구현하였지만, 자꾸 틀렸습니다라고 해서

도데체 무슨 오류인지 몰라서 고민하다가

책을 참조해보니 부모노드가 pointer/2가 아니라 (pointer-1)/2라는 것을 알게 되었다. 

그래도 계속 틀렷다고 해서 모든 값을 가진 최대힙을 구현해서 n만큼 pop울 해줬다.

아직까지도 왜 처음 시도였던 n개의 최소힙이 성공이 안 됫는지 모른다.

부모 노드는 (pointer-1)/2이다!!

#include <stdio.h>
int list[2250010] = { 0 };
int pp = 0;
void swap(int i, int j) {
	int temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}
void insert_heap(int value) {
	list[pp] = value;
	int pointer = pp++;
	while (1) {
		if (list[pointer] <= list[(pointer-1) / 2])
			return;
		swap(pointer, (pointer-1) / 2);
		pointer = (pointer - 1) / 2;
	}
}
int delete_haap() {
	int box = list[0];
	list[0] = list[--pp];
	list[pp] = 0;
	int pointer = 0;
	while (1) {
		if (pointer * 2 + 2 >= 2250010)
			break;
		if (list[pointer * 2 + 1] == 0 && list[pointer * 2 + 2] == 0)
			break;
		if (list[pointer * 2 + 1] > list[pointer * 2 + 2]) {
			swap(pointer * 2 + 1, pointer);
			pointer = pointer * 2 + 1;
		}
		else {
			swap(pointer * 2 + 2, pointer);
			pointer = pointer * 2 + 2;
		}
	}
	return box;
}
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	int number = 0;
	int buffer = 0;
	int count = 0;
	scanf("%d", &number);
	for (int i = 0; i < number * number; i++) {
		scanf("%d", &buffer);
		insert_heap(buffer);
	}
	for (int i = 0; i < number - 1; i++)
		delete_haap();
	printf("%d\n", delete_haap());
	return 0;
}