BOJ - 11279번 최대 힙

문제 출처: https://www.acmicpc.net/problem/11279

문제 접근법

Heap을 이해하고 직접 구현해보자.
문제에서 필요한 Insert 함수와 Delete 함수를 구현해야하는데 주의할 점은
Insert : UpHeap이 필요함, 추가된 노드 값으로 Parent와 비교해서 child가 부모 값보다 크면 바꿔준다. 더 큰 값이 없을 때까지
delete : DownHeap이 필요함, 삭제할 상위 노드를 빼놓고 상위 노드를 채우기 위해 맨 마지막 노드까지 내려가 값을 비교한다.

통과 코드

#include <iostream>

#define INF 987654321

using namespace std;

int heapSize;
int heap[100001];

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void insert_heap_node(int x) {
	heap[++heapSize] = x;
	int child = heapSize;
	int parent = child / 2;

	//UpHeap
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[child], &heap[parent]);
		child = parent;
		parent = child / 2;
	}
}

int pop() {
    if(heapSize == 0) return 0;
	int result = heap[1];
	swap(&heap[1], &heap[heapSize]);
	heapSize--;
	//DownHeap
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heapSize) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}
	while (child <= heapSize && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		parent = child;
		child = parent * 2;
		if (child + 1 <= heapSize) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}
	return result;
}

int main() {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		if (x == 0) {
			printf("%d\n", pop());
		}
		else insert_heap_node(x);
	}
	

	return 0;
}

피드백

자꾸 시간초과가 나서 역시 우선순위 큐로 풀어야하나.. 했다. 그래서 설마하고 scanf와 print로 바꾸니깐 통과했다.. c++ 입출력의 소요 시간이란..