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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static class Heap {
		int heap[];
		int size;

		public Heap(int size) {
			heap = new int[size];
		}

		public void add(int x) {
			heap[++size] = x; 

			for (int i = size; i > 1 ; i = i/2) {
				if (heap[i / 2] > heap[i]) { 
					swap(i/2, i);
				} else {
					break;
				}
			}
		}

		public int delete() {
			if (size == 0) {
				return 0;
			}

			int root = heap[1];
			heap[1] = heap[size];
			size--; 

			for (int i = 1; 2*i <= size ; ) {
				if ( ( heap[i] < heap[i * 2] )&& ( heap[i] < heap[i * 2 + 1] )) {
					break;

				} else if (heap[i * 2 + 1] > heap[i * 2] ) { // 왼이 오보다 작으면
					swap(i, i * 2); 
					i *=  2;
				} else {
					swap(i, i * 2 + 1);
					i = i * 2 + 1;
				}
			}
			return root;
		}

		public void swap(int a, int b) {
			int temp = heap[a];
			heap[a] = heap[b];
			heap[b] = temp;
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		Heap h = new Heap(100001);

		for (int i = 0; i < N; i++) {
			int x = Integer.parseInt(br.readLine());
			if (x == 0) {
				System.out.println(h.delete());
			} else {
				h.add(x);
			}

		}

	}

}