BOJ. Maximum heap (11279)

[Link] https://www.acmicpc.net/problem/11279

A max-heap keeps every parent value greater than or equal to its children, so the largest value is always at the root. Inserting a value appends it at the end and sifts it upward while it is larger than its parent. Removing the maximum replaces the root with the last value and sifts that value downward by swapping with the larger child. Each operation follows at most one root-to-leaf path, so insertion and removal take O(log N) time. The primitive array uses O(N) space; its capacity is enough for the maximum possible number of insert commands.

The input is read as whitespace-separated tokens, and all results are accumulated in a StringBuilder. A removal from an empty heap prints 0, as required.

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

public class Main {
  private static BufferedReader reader =
      new BufferedReader(new InputStreamReader(System.in));
  private static StringTokenizer tokenizer;

  private static int nextInt() throws IOException {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine());
    }
    return Integer.parseInt(tokenizer.nextToken());
  }

  public static void main(String[] args) throws IOException {
    int n = nextInt();
    int[] heap = new int[n + 1];
    int size = 0;
    StringBuilder output = new StringBuilder();

    for (int i = 0; i < n; i++) {
      int value = nextInt();
      if (value == 0) {
        if (size == 0) {
          output.append(0).append('\n');
        } else {
          output.append(heap[1]).append('\n');
          heap[1] = heap[size--];

          int parent = 1;
          while (parent * 2 <= size) {
            int child = parent * 2;
            if (child + 1 <= size && heap[child + 1] > heap[child]) {
              child++;
            }
            if (heap[parent] >= heap[child]) {
              break;
            }
            int temp = heap[parent];
            heap[parent] = heap[child];
            heap[child] = temp;
            parent = child;
          }
        }
      } else {
        int child = ++size;
        while (child > 1 && heap[child / 2] < value) {
          heap[child] = heap[child / 2];
          child /= 2;
        }
        heap[child] = value;
      }
    }

    System.out.print(output);
  }
}