题解 | 【模板】堆

import java.util.Scanner;

public class Main {
    private static int[] heap = new int[100010]; // 堆数组
    private static int size = 0; // 当前堆大小

    // 获取父节点索引
    private static int parent(int i) {
        return i / 2;
    }

    // 获取左孩子索引
    private static int left(int i) {
        return 2 * i;
    }

    // 获取右孩子索引
    private static int right(int i) {
        return 2 * i + 1;
    }

    // 交换两个元素
    private static void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 上浮操作
    private static void siftUp(int i) {
        while (i > 1 && heap[i] > heap[parent(i)]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    // 下沉操作
    private static void siftDown(int i) {
        int maxIndex = i;
        int l = left(i);
        int r = right(i);

        if (l <= size && heap[l] > heap[maxIndex]) {
            maxIndex = l;
        }
        if (r <= size && heap[r] > heap[maxIndex]) {
            maxIndex = r;
        }

        if (i != maxIndex) {
            swap(i, maxIndex);
            siftDown(maxIndex);
        }
    }

    // 插入元素
    private static void push(int x) {
        if (size >= heap.length - 1) return; // 防止溢出
        size++;
        heap[size] = x;
        siftUp(size);
    }

    // 获取堆顶
    private static void top() {
        if (size == 0) {
            System.out.println("empty");
        } else {
            System.out.println(heap[1]);
        }
    }

    // 弹出堆顶
    private static void pop() {
        if (size == 0) {
            System.out.println("empty");
        } else {
            System.out.println(heap[1]);
            heap[1] = heap[size];
            size--;
            siftDown(1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine(); // 消耗换行符

        for (int i = 0; i < n; i++) {
            String line = sc.nextLine().trim();
            if (line.startsWith("push")) {
                int x = Integer.parseInt(line.split(" ")[1]);
                push(x);
            } else if (line.equals("top")) {
                top();
            } else if (line.equals("pop")) {
                pop();
            }
        }
    }
}