백준 11279번 최대 힙(C++)

 자료구조 힙, 우선순위 큐, 그리디 문제를 열심히 풀어보려고 한다. 먼저 최대힙 문제를 풀어봤다. 

우선순위큐를 구현하기 위해 생긴 자료구조가 힙이다. 힙은 이진트리로 구성되어있고 배열 혹은 리스트로 구현이 가능하다. 물론 이 문제는 힙같은건 구현할 필요 없고 stl만 사용해도 충분하지만 공부를 위해 배열로 구현해봤다.

 

기본적인 최대힙의 개념을 살펴보면

1. 부모노드는 언제나 자식 노드보다 크다.

2. 자식 노드 중 작은 노드가 왼쪽 더 큰 노드가 오른쪽이다.

 

이러한 배열이 있다고 치면

index	1	2	3	4	5	6
value	1	3	6	5	9	8

이걸 트리 형태로 만들어보면

 

                                          1

                                         /    \

                                       3      6

                                      / \     / 

                                    5   9  8

 

 이렇게 될 것이다. 그러니까

부모노드의 index = 자식노드의 index / 2

자식노드의 index = 부모노드의 index * 2 or 부모노드의 index * 2 + 1

라는 공식이 된다. 이 공식으로 insert 와 delete 연산이 된다.

 

먼저 stl 답안 -

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> answer;
int main() {
	priority_queue<int> pq;
	int cnt = 0;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		if (tmp == 0) {
			if (!pq.empty()) {
				answer.push_back(pq.top());
				pq.pop();
			}
			else
				answer.push_back(0);
		}
		else {
			pq.push(tmp);
		}
	}
    for(auto a : answer)
        cout << a << '\n';
}

배열로 구현한 답안 -

#include <iostream>
#include <vector>
using namespace std;
vector<int> answer;
int heap_cnt = 0;
int Array[100001];
void swap(int *a, int *b){
	int t;
	t = *a;
	*a = *b;
	*b = t;
}

int size() {
	return heap_cnt;
}

void heap_push(int data) {
	Array[++heap_cnt] = data;
	int child = heap_cnt;
	int parents = child / 2;
	while (child > 1 && Array[parents] < Array[child]) {
		swap(&Array[parents], &Array[child]);
		child = parents;
		parents = child / 2;
	}
}

void heap_pop() {
	int top = Array[1];
	swap(&Array[1], &Array[heap_cnt]);
	heap_cnt--;

	int parants = 1;
	int child = parants * 2;
	if (child + 1 <= heap_cnt) {
		child = (Array[child] > Array[child + 1]) ? child : child + 1;
	}

	while (child <= heap_cnt && Array[parants] < Array[child]) {
		swap(&Array[parants], &Array[child]);
		parants = child;
		child = child * 2;
		if (child + 1 <= heap_cnt) {
			child = (Array[child] > Array[child + 1]) ? child : child + 1;
		}
	}
	answer.push_back(top);
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;

		if (tmp == 0) {
			if (heap_cnt == 0)
				answer.push_back(0);
			else {
				heap_pop();
			}
		}
		else 	
			heap_push(tmp);
	}
	for (auto a : answer)
		cout << a << '\n';
}

시간차이가 나는 이유는 ios:: 이거 붙히고 안붙히고 차이이다.