[알고리즘][C++] 우선순위큐, 힙큐

백준 11279: 최대 힙

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

11279번: 최대 힙

 

 

접근 방향 및 디버깅

[1] 최대힙 깡구현

- insert(), pop() 시 트리를 상/하단으로 탐색하여 아이템 간 대소비교를 통해 값 swap 하는 전역 함수 생성

- insert() 시에는 값을 최하단 노드에 추가하여, 부모 노드가 나보다 값이 나보다 클 때까지 swap

- pop() 시에는 최상단 값을 제거하고, 자식 노드가 나보다 값이 작을 때까지 swap

 

[2] 라이브러리 활용

- queue 라이브러리의 priority_queue 활용

- 기타 로직은 동일

 

[3] 출력 이슈

- [1], [2] 모두 최초 제출은 시간 초과로 실패했으나, 로직상 문제가 없다고 판단하여 질문게시판을 확인함. 

- https://www.acmicpc.net/board/view/22716 답변 확인하여, C++ 의 입출력 관련 코드 추가

- [1], [2] 코드로 제출 모두 성공

 

코드

/* [1] 2412kb, 12ms */
#define MAX 100001
#include <cstdio>
#include <iostream>

using namespace std;

int h[MAX];
int cnt = 0;

void swap(int i, int j) {
	int t = h[i];
	h[i] = h[j];
	h[j] = t;
}

void upHeapify(int i) {
	if (i == 1) return;

	if (h[i] > h[i / 2]) {
		swap(i, i / 2);
		upHeapify(i / 2);
	}
}

void downHeapify(int i) {

	int temp;

	if (i * 2 > cnt) return;

	if (i * 2 + 1 <= cnt) {
		if (h[i * 2] > h[i * 2 + 1]) {
			temp = i * 2;
		}
		else {
			temp = i * 2 + 1;
		}
	}
	else {
		temp = i * 2;
	}

	if (h[temp] > h[i]) {
		swap(i, temp);
		downHeapify(temp);
	}

}

void insert(int data) {
	h[++cnt] = data;
	upHeapify(cnt);
}

void pop() {
	h[1] = h[cnt--];
	downHeapify(1);
}

int main() {
	freopen("input.txt", "r", stdin);
	
	int N;
	cin >> N;
	

	for (int i = 0; i < N; i++) {
		int data;
		cin >> data;

		if (data > 0) {
			insert(data);
		}
		else {
			if (cnt > 0) {
				cout << h[1] << "\n";
				pop();
			}
			else {
				cout << 0 << "\n";
			}
		}
	}

	return 0;
}

/* [2] 2916KB, 16ms */

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	freopen("input.txt", "r", stdin);

	int N;
	cin >> N;

	priority_queue<int> q;

	for (int i = 0; i < N; i++) {
		int data;
		cin >> data;

		if (data > 0) {
			q.push(data);
		}
		else {
			if (q.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
	}

	return 0;
}

 

배운 점

- 성능을 높여주는 여러 코드의 위력을 간과하지 말기 (ios_base::sync_with_stdio(false) 등)

- 깡구현이 힘들어도 메모리나 실행 속도 성능은 더 잘 나온다. 템플릿 외워두자.