[백준] 1927 최소 힙 (C++)

백준 1927 최소 힙 문제
백준 1927 최소 힙 소스코드

📄 문제 설명

Problem

널리 잘 알려진 자료구조 중 최소 힙이 있다.
최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

Input

첫째 줄 : 연산의 개수 N(1 ≤ N ≤ 100,000)
다음 N개의 줄 : 연산에 대한 정보를 나타내는 정수 x

만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고,
x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
입력되는 자연수는 2^31보다 작으며, 음의 정수는 입력으로 주어지지 않는다.

Output

입력에서 0이 주어진 회수만큼 답을 출력한다.
만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

Example Input

9
0
12345678
1
2
0
0
0
0
32

Example Output

0
1
2
12345678
0

📝 문제 해설

이 문제는 최소 힙을 구현하는 문제이다.

▶ 힙 (Heap)

힙은 ✔<완전 이진트리> 형태의 자료구조로 <힙 조건(Heap Condition)>을 만족한다.
주로 일차원 배열로 구현되며, 일반적으로 그룹을 정렬(Heap Sort)하거나,
입력된 데이터 안에서 <최소/최대 값>을 찾을 때 사용한다.
데이터의 삽입과 삭제가 빠르며 수행시간이 O(log N)이다.

✔ 이진 트리(Binary Tree) : 트리의 차수가 2이하인 트리

✔ 정 이진 트리(Full Binary Tree) : 모든 노드의 차수가 0 또는 2인 이진 트리

✔ 포화 이진 트리 (Perfect Binary Tree): 정 이진 트리에서모든 단말 노드의 깊이가 같은 이진 트리

✔ 완전 이진 트리 (Complete Binary Tree): 마지막 레벨은 노드가 왼쪽에 몰려있고 마지막 레벨을 제외하면 포화 이진 트리 구조를 띄고 있는 이진 트리.

▶ 최소 힙 (Min Heap)

최소 힙은 "부모노드의 키 값이 자식 노드의 키 값보다 항상 작다"는 힙조건을 가지고 있다.
부모노드의 키 값이 자식노드의 키 값보다 작은 관계가 유지되므로 트리 내에서 가장 작은 값은
항상 root 노드가 된다.

최소 힙의 삽입

최소 힙에 새로운 값(x)을 삽입할 때
ⓐ 가장 마지막 노드로 삽입한다.
ⓑ x가 부모 노드보다 작을 때 부모 노드와 SWAP (반복)
ⓒ x가 부모 노드보다 클 때 그 자리가 x의 자리가 된다.

최소 힙의 삭제

최소 힙에서 값을 삭제할 때
ⓐ root 노드를 삭제한다.
ⓑ root 노드에 마지막 노드를 삽입한다.
ⓒ 그 노드가 자식 노드보다 값이 더 크다면 (왼쪽 오른쪽 자식 중) 더 작은 값과 SWAP (반복)

</> Source Code

#include <bits/stdc++.h>

using namespace std;

int n;
vector<long> heap;

void pop(){
	if(heap.size() > 1){
		printf("%d\n", heap[1]);
		
		int node = 1, lastIdx = heap.size() - 1;
		heap[node] = heap[lastIdx];
		heap.erase(heap.begin() + lastIdx);
		
		while(true){
			int left = node * 2, right = node * 2 + 1;
			if(left >= lastIdx) break;
			
			int minV = heap[left], minPos = left;
			
			if(right < lastIdx && heap[right] < minV){
				minV = heap[right];
				minPos = right;
			}
			
			if(minV < heap[node]){
				swap(heap[minPos], heap[node]);
				node = minPos;
			}else{
				break;
			}
		}				
	}else{
		printf("0\n");
	}
}

void push(int x){
	heap.push_back(x);
	int node = heap.size() - 1, parent = node / 2;
	
	while(true){
		if(node == 0 && heap[node] > heap[parent]) break;
		
		if(heap[node] < heap[parent]){
			swap(heap[node], heap[parent]);
			node = parent;
			parent = node / 2;
		}else{
			break;
		}
	}
}

int main(){

	scanf("%d", &n);
	heap.push_back(0);
	
	for(int i = 0; i < n; i++){
		int x;
		scanf("%d", &x);
		
		if(x == 0){	
			pop();
		}else{
			push(x);
		}
	}
	
	return 0;
}