[백준 알고리즘/BOJ] 자바(java) 1927번 최소 힙

1927번: 최소 힙

 

문제

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

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

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

 

 

 

package baekjoon;
import java.io.*;
import java.util.*;

public class B_1927 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		minHeap heap = new minHeap();
		int n = Integer.parseInt(br.readLine());
		for(int i=0;i<n;i++) {
			int input = Integer.parseInt(br.readLine());
			if(input == 0) {
				System.out.println(heap.delete());
			}
			else
				heap.insert(input);
		}
	}
}

class minHeap {
	private ArrayList<Integer> heap;
	public minHeap() {
		heap = new ArrayList<Integer>();
		heap.add(0); // 인덱스 0은 사용하지 않음
	}
	public void insert(int val) {
		heap.add(val);
		int p = heap.size()-1; // 현재 삽입한 노드의 위치 저장
		while(p > 1 && heap.get(p) < heap.get(p/2)) {
			// 삽입한 노드가 루트 노드가 아니고 부모가 자식보다 크면
			int tmp = heap.get(p/2);
			heap.set(p/2, val);
			heap.set(p, tmp);
			// 부모와 자식 위치 변경

			p /= 2;
		}
	}
	public int delete() {
		if(heap.size()-1 < 1)
			return 0;

		int del = heap.get(1);
		// 루트 노드를 삭제

		heap.set(1, heap.get(heap.size()-1));
		heap.remove(heap.size()-1);
		// 마지막 노드를 루트에 삽입하고 마지막 노드 삭제

		int p = 1; // 현재 삭제한 노드의 위치 (루트 노드)

		while(p * 2 < heap.size()) {
			// 자식이 힙 사이즈를 벗어날 때까지 while문 반복
			int min = heap.get(p*2); // 왼쪽 자식의 값
			int minP = p*2; // 왼쪽 자식의 인덱스

			if(2*p+1 < heap.size() && min > heap.get(2*p+1)) {
				// 오른쪽 자식이 왼쪽 자식보다 작고 힙 사이즈를 벗어나지 않으면
				min = heap.get(2*p+1);
				minP = 2*p+1;
			}
			if(heap.get(p) < min)
				break; // 부모가 더 작으면 빠져나옴

			int tmp = heap.get(p);
			heap.set(p, min);
			heap.set(minP, tmp);
			p = minP;
			// 부모와 자식 위치 변경
		}
		return del;
	}
}