题解 | #【模板】堆#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static final StringBuilder sb = new StringBuilder();

    static class Heap {
        // 记录堆的实际长度,可以节省出堆的操作。
        private int size;
        private final ArrayList<Integer> list;

        public Heap() {
            //利用动态数组存储堆
            list = new ArrayList<>();
            size = 0;
        }

        public void push(int x) {
            //添加新元素到最后
            list.add(x);
            size++;
            //从最后一个非叶子结点开始向上调整
            for (int i = size / 2 - 1; i >= 0; i = (i - 1) / 2) {
                adjustHeap(i);
                //这里是由于（i-1）/2取下整，当i=0会出现死循环
                if (i == 0) break;
            }
        }

        public void pop() {
            if (size == 1) {
                int first = list.remove(0);
                sb.append(first).append("\n");
                size--;
            } else if (size > 1) {
                int last = list.get(size-1);
                int first = list.get(0);
                sb.append(first).append("\n");
                list.set(0, last);
                list.remove(size-1);
                size--;
                adjustHeap(0);
            } else {
                sb.append("empty").append("\n");
            }
        }

        public void top() {
            if (size <= 0) {
                sb.append("empty").append("\n");
            } else {
                sb.append(list.get(0)).append("\n");
            }
        }
        //向下调整
        private void adjustHeap(int i) {
            int temp = list.get(i);
            for (int k = 2 * i + 1; k < size; k = 2 * k + 1) {
                //取孩子中较大的与之比较
                if (k + 1 < size && list.get(k) < list.get(k + 1)) {
                    k++;
                }
                int larger = list.get(k);
                if (larger > temp) {
                    list.set(i, larger);
                    i = k;
                } else {
                    break;
                }
            }
            list.set(i, temp);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in));
        int commandCount = Integer.parseInt(br.readLine());
        Heap heap = new Heap();
        for (int i = 0; i < commandCount; i++) {
            String[] array = br.readLine().split(" ");
            String command = array[0];
            if (command.equals("push")) {
                heap.push(Integer.parseInt(array[1]));
            } else if (command.equals("pop")) {
                heap.pop();
            } else if (command.equals("top")) {
                heap.top();
            }
        }
        System.out.println(sb);
    }
}