[백준] 11279번 최대 힙

 

 

 

 

문제

 

소스코드

#include<iostream>
#include<vector>
constexpr int MAX_INDEX = 1000002;
std::vector<int> read_v;

class Heap {
private:
	int value_[MAX_INDEX];
	int size_;
	void Swap(int& lhs, int& rhs) {
		int temp = lhs;
		lhs = rhs;
		rhs = temp;
	}
public:
	Heap() :size_(0) {
		for (int i = 0; i < MAX_INDEX; ++i) {
			value_[i] = -1;
		};
	}
	int GetNode(int curr) {
		int left = curr * 2;
		int right = curr * 2 + 1;

		// 자식이 없다.
		if (left > size_) {
			return 0;
		}
		//왼쪽 자식만 있다.
		else if (left == size_) {
			return left;
		}

		//자식이 둘다 있다.
		else {
			if (value_[left] > value_[right])
				return left;
			else
				return right;
		}
	}

	void Pop() {
			if (size_ == 0) {
				read_v.emplace_back(0);
			}
			else {
				int	highValue = value_[1];
				int index = size_;
				int curr = 1;
				value_[1] = value_[index];

				//위에서 아래로 
				while (int node = GetNode(curr)) {
					//자식 노드가 더 크다면 바꾼다.
					if (value_[node] > value_[curr]) {
						Swap(value_[node], value_[curr]);
						curr = node;
					}
					else
						break;
				}
				--size_;
				read_v.emplace_back(highValue);
			}
	}

	//처음에 값을 넣을 때 맨 마지막에 넣는다.
	void Push(int value) {
		//값을 제거하고 출력한다.
		if (value == 0) {
			Pop();
		}
		else {
			int index = size_ + 1;
			value_[index] = value;
			int parent = index / 2;
			
			//아래에서 위로 이동
			while (index!=1) {
				if (value_[index] > value_[parent]) {
					Swap(value_[index], value_[parent]);
					index = parent;
					parent = index / 2;
				}
				else
					break;
			}
			++size_;
		}
	}
};

/*
1. 입력된 N까지 값을 넣는다.

2. 0을 입력하면 배열에서 가장 큰값을 출력하고 그 값을 배열에서 제거하는 경우이다.

3. 출력은 마지막에 진행되기 때문에 출력 전용 컨테이너를 만든다.
*/


Heap list{};
int main() {
	int n, x;
	std::cin >> n;
	read_v.reserve(MAX_INDEX);
	for (int i = 0; i < n; ++i) {
		std::cin >> x;
		list.Push(x);
	}
	for (auto& i : read_v)
		std::cout << i << "\n";

}

 

 

후기

이 문제를 해결하기 위해서는 Heap 자료구조를 알고 있어야 한다.

Heap 자료구조를 알고 있다면 손쉽게 풀 수 있다.

STL 자료구조인 우선순위 큐를 사용하지 않고 자체 최대 힙을 구현해서 풀었다.

 

*배열의 시작을 1부터 한다면 최대 크기를 주의해야 한다.

 

질문 검색 글에 반례가 없기 때문에 몇 개 만든 것을 여기에 공유합니다.

 

우선순위 큐 반례.txt

0.00MB

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/11279

 

관련 자료구조 글

우선순위 큐(Priority Queue)