백준 11279 - 최대 힙

C++

11279 번 - 최대 힙

문제

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

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 입력에서 0이 주어진 회수만큼 답을 출력한다.
   만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

문제 출처

접근 방법

최대 힙의 개념과 응용 방법에 대해 제시하는 문제이다.
최소 힙와 동일한 문제로, 최대 값이 Root Node가는 최대 힙이다.

구현

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

코드

#include <iostream>
#include <vector>

using namespace std;

class MaxHeap {
private:
	int size;
	int* arr;
public:
	MaxHeap(int maxSize) {
		size = 0;
		arr = new int[maxSize];
	}
	int Delete() {
		if (size == 0)
			return -1;
		int retV = arr[1];
		int parent = 1, child;
		arr[1] = arr[size];
		size--;
		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 retV;
	}
	void Insert(int data) {
		int here = ++size;
		while (here != 1 && data > arr[here / 2]) {
			arr[here] = arr[here / 2];
			here /= 2;
		}
		arr[here] = data;
	}
};
int n;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

총평

난이도

⭐★★★★

후기

최소 힙을 통해 공부한 내용을 복기하며 최대 힙 클래스를 구현하였다.

개선할 점

차후 절댓값 힙 문제를 통해 복습 할 필요가 있다.