백준 1927 - 최소 힙

C++

1927 번 - 최소 힙

문제

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

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

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

문제 출처

접근 방법

최소 힙의 개념과 응용 방법에 대해 제시하는 문제이다.
참고 블로그를 통하여 최소 힙에 대하여 공부하여 문제를 해결하였다.

구현

Heap에 대한 구조와 Insert / Delete를 Class로 구현하여 이후에도 사용할 수 있도록 만들었다.

코드

#include <iostream>
#include <vector>

using namespace std;

class MinHeap {
private:
	int size;
	int* arr;
public:
	MinHeap(int maxNum) {
		size = 0;
		arr = new int[maxNum];
	}
	int Delete() {
		if (size == 0)
			return -1;
		int ret = arr[1];
		arr[1] = arr[size];
		size--;
		int parent = 1, child;
		while (1) {
			child = parent * 2;
			// 현재 부모 노드와 자식 노드 중 어느 자식 노드와 교체 할 것인지 정하는 조건문
			// 두번째 자식 노드가 더 작은 수면, 두번째 자식 노드와 교체한다.
			if (child + 1 <= size && arr[child] > arr[child + 1])
				child++;
			// 탈출 조건
			if (child > size || arr[child] > arr[parent])
				break;
			swap(arr[child], arr[parent]);
			parent = child;
		}
		return ret;
	}
	// 트리의 가장 마지막에 값을 넣고, 부모와 비교하며 놓을 자리를 찾는다.
	void Insert(int num) {
		int here = ++size;				//size를 1 증가시키며, 삽입할 위치로 정한다.
		while (here != 1 && num < arr[here / 2]) {
			arr[here] = arr[here / 2];
			here /= 2;
		}
		arr[here] = num;
	}
};
int n;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	int curN;
	MinHeap minHeap = MinHeap(100001);
	while (n--) {
		cin >> curN;
		// Delete
		if (curN == 0) {
			int delR = minHeap.Delete();
			if (delR == -1)
				cout << "0" << "\n";
			else
				cout << delR << "\n";
		}
		// Insert
		else {
			minHeap.Insert(curN);
		}
	}
	return 0;
}

총평

난이도

⭐⭐★★★

후기

Heap에 대한 공부를 하게 하는 문제.
타인의 코드를 통해 구현해 보았지만, 차후에 내가 이해하는 코드로 습득 할 필요가 있다.

개선할 점

Heap 클래스의 Delete 메소드에서 size 조건을 좀 더 이해 해야한다.