백준 11279 최대 힙

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

 

서론

최대 힙에 관한 문제라서 최대 힙을 구현해봤다.

시간초과가 발생해서 무한루프를 예상하고 원인을 매우 아주 상당히 오래 찾았으나 cin, cout의 속도로 인한 문제였다.

printf, scanf 를 사용하여 해결했다.

 

---

구현

// c++
// max heap

#pragma warning (disable:4996)

#include <iostream>
#include <cstdio>

typedef struct pq {
	int heap[100003] = { 0, };
	int index = 0;
}pq;

void push(pq *q, int item) {
	q->index++;
	q->heap[q->index] = item;

	int index = q->index;
	while (q->heap[index] > q->heap[index / 2]) {
		if (index == 1) break;
		int tmp = q->heap[index];
		q->heap[index] = q->heap[index / 2];
		q->heap[index / 2] = tmp;
		index /= 2;
	}
}

void pop(pq *q) {
	if (q->index == 0) return;
	q->heap[1] = q->heap[q->index];
	q->heap[q->index] = 0;
	q->index--;

	int index = 1;
	while (index * 2 <= q->index) {
		int nextIndex = 0;
		if (q->heap[index * 2] >= q->heap[index * 2 + 1]) nextIndex = index * 2;
		else nextIndex = index * 2 + 1;

		if (q->heap[nextIndex] > q->heap[index]) {
			int tmp = q->heap[index];
			q->heap[index] = q->heap[nextIndex];
			q->heap[nextIndex] = tmp;
			index = nextIndex;
		}
		else break;
	}

}

int top(pq *q) {
	if (q->index == 0) return 0;
	else return q->heap[1];
}


int main() {
	pq q;
	int n;
	std::cin >> n;
	while (n--) {
		int x;
		//std::cin >> x;
		scanf("%d", &x);
		if (x == 0) { 
			//std::cout << top(&q) << std::endl; 
			printf("%d\n", top(&q));
			pop(&q);
		}
		else push(&q, x);
	}
}