[백준] 1927번 : 최소 힙

문제

 

 

접근 방식

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

C++의 STL이나 자바의 유틸 클래스에 이미 구현된 우선순위 큐를

사용해서 편하게 풀 수도 있지만 구현해봐야 어떤 원리로

동작하는지를 이해하기 쉽기 때문에 직접 구현해봤다.

 

최소 힙은 부모가 자식보다 작은 값을 가지고 있는 이진 트리 구조여야 하기 때문에

새로운 값을 추가할 때는 가장 마지막 자식 노드에 값을 추가한 후에

해당 노드가 부모 노드보다 큰지 검사하면서 만약 더 작다면 부모 노드와 바꿔주면 된다.

 

반대로 가장 작은 값을 하나 꺼낼 때는 최소 힙의 구조상 무조건 최상위 부모 노드가

가장 작은 값에 해당하기 때문에 해당 값을 출력하고 삭제해주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());

		MinHeap minHeap = new MinHeap();

		while (n-- > 0) {
			int x = Integer.parseInt(br.readLine());

			if (x != 0) minHeap.offer(x);
			else sb.append(minHeap.poll()).append("\n");
		}

		System.out.println(sb);
	}

	private static class MinHeap {
		int[] heap = new int[100001];
		int size = 0;

		void offer(int x) {
			heap[++size] = x;
			int idx = size;

			while (idx != 1) {
				int cur = idx/2;

				if (heap[idx] > heap[cur]) break;

				swap(idx, cur);

				idx = cur;
			}
		}

		int poll() {
			if (size == 0) return 0;

			int r = heap[1];
			heap[1] = heap[size--];
			int idx = 1;

			while (idx * 2 <= size) {
				int left = idx * 2;
				int right = left + 1;
				int min = left;

				if (right <= size && heap[right] < heap[left]) min = right;
				if (heap[min] >= heap[idx]) break;

				swap(min, idx);

				idx = min;
			}

			return r;
		}

		void swap(int x, int y) {
			int tmp = heap[x];
			heap[x] = heap[y];
			heap[y] = tmp;
		}
	}
}