题解 | #【模板】堆#

注意事项:

1. 除了 top 操作，push 操作和 pop 操作都要进行 堆的调整。你在 插入 一个新数据，亦或者是 弹出 堆顶元素，都别忘记 调整堆的结构。无论何时，你用来存储 大根堆 的结构，都一定要满足大根堆的性质
2. 对于当前代码，可以进行 优化。优化的地方，就是每次 弹出 堆顶元素之后，不要 删除 该位置上的元素，而是先将 堆顶元素 与 堆尾元素 进行交换，再删除该元素。因为对于 ArrayList 结构来说，每一次 remove，如果 remove 的位置向后有许多元素，都需要进行移动，最坏情况下，n长度的数组，移除 下标为0 位置上的元素，需要移动 n-1 个元素。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.valueOf(scan.nextLine().trim());
        ArrayList<String> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] operator = scan.nextLine().split(" ");
            if ("push".equals(operator[0])) {
                push(Integer.valueOf(operator[1]));
            } else if ("top".equals(operator[0])) {
                ans.add(top());
            } else {
                ans.add(pop());
            }
        }
        for (String str : ans) {
            System.out.println(str);
        }
    }
    public static ArrayList<Integer> heap = new ArrayList<>();
    public static void push(int x) {
        heap.add(x);
        heapInsert(heap.size() - 1);
    }
    public static String top() {
        return heap.isEmpty() ? "empty" : String.valueOf(heap.get(0));
    }
    public static String pop() {
        if (heap.isEmpty()) {
            return "empty";
        } else {
            String str = String.valueOf(heap.get(0));
            swap(0, heap.size() - 1);
            heap.remove(heap.size() - 1);
            heapify(0, heap.size());
            return str;
        }
    }
    public static void heapInsert(int index) {
        while (heap.get(index) > heap.get((index - 1) / 2)) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    public static void heapify(int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && heap.get(left + 1) > heap.get(left) ? left + 1 : left;
            largest = heap.get(largest) > heap.get(index) ? largest : index;
            if (largest == index) {
                break;
            }
            swap(largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
    public static void swap(int p1, int p2) {
        int tmp = heap.get(p1);
        heap.set(p1, heap.get(p2));
        heap.set(p2, tmp);
    }
}