[11279] 최대 힙

최대 힙

    각 노드의 키 값이 자식의 키 값보다 작지 않은 트리.

    최대 트리 & 완전 이진 트리

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) throws IOException {
   		// 자바에서 priorityQueue는 기본적으로 최소힙으므로 역순
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++) {
			int a = Integer.parseInt(br.readLine());
			
			if(a == 0) {
				if(q.isEmpty()) {
					bw.write("0\n");
				} else {
					bw.write(Integer.toString(q.poll()) + "\n");
				}
			} else {
				q.add(a);
			}
		}
		bw.flush();
		bw.close();
	}
}

자바에서 PriorityQueue 라이브러리를 제공하는걸 모른다면 직접 구현해서 풀어야하는 문제