BOJ. Maximum heap (11279)

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    Heap heap = new Heap();
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = atoi(br.readLine());
    for(int i = 0; i < N; i++) {
      int n = atoi(br.readLine());
      if(n == 0) sb.append(heap.pop()).append("\n");
      else heap.insert(n);
    }
    System.out.println(sb);
  }

  public static class Heap{
    ArrayList<Integer> al = new ArrayList<>();
    int size;

    Heap() { al.add(null); }

    void insert(int val) {
      al.add(val);
      int idx = al.size() - 1;
      while(idx / 2 >= 1) {
        int pIdx = idx / 2;
        int parent = al.get(pIdx);
        if(parent < val) {
          al.set(pIdx, al.get(idx));
          al.set(idx, parent);
        } else break;
        idx = pIdx;
      }
    }

    int pop() {
      int size = al.size(), idx = 1;
      if(size <= 1) return 0;
      int v = al.get(size - 1);
      int topV = al.set(1, v);
      al.remove(size - 1);
      size--;
      while(idx * 2 < size) {
        int l = idx * 2, r = l + 1, maxIdx;
        if(r < size) maxIdx = al.get(l) > al.get(r) ? l : r;
        else maxIdx = l;
        if(al.get(maxIdx) <= v) break;
        al.set(idx, al.get(maxIdx));
        al.set(maxIdx, v);
        idx = maxIdx;
      }
      return topV;
    }
  }

  private static int atoi(String s) { return Integer.parseInt(s); }
}