题解 | #【模板】堆#

大根堆的概念

大根堆是一种特殊的完全二叉树结构，其中每个节点的值都大于或等于其子节点的值。在数组表示的堆中，对于任意节点i（从0开始计数），其左子节点的位置为2i+1，右子节点的位置为2i+2，而其父节点的位置为(i-1)/2。

大根堆的操作

1. Push（插入）：向堆中添加一个新的元素。
2. Top（获取最大值）：返回堆顶的元素，也就是当前堆中的最大值。
3. Pop（删除最大值）：移除堆顶的元素，并返回该值。

如何插入元素（Push）

当向堆中插入一个新元素时，我们首先将该元素添加到数组的末尾，然后执行上浮操作（Sift Up）。上浮操作是从叶子节点向上比较并交换节点与其父节点，直到满足堆的性质为止。

如何获取最大值（Top）

由于大根堆总是把最大的元素放在数组的第一个位置（即索引为0的位置），所以我们只需要返回数组的第一个元素即可。

如何删除最大值（Pop）

删除堆顶元素时，我们先记录下堆顶元素的值，然后将数组的最后一个元素移到堆顶，接着从堆顶开始执行下沉操作（Sift Down）。下沉操作是从根节点向下比较并交换节点与其较大的子节点，直到满足堆的性质为止。

算法重点：

1. 数组表示的完全二叉树：使用数组来表示堆，其中每个元素的位置都有确定的关系：对于任意节点i（从0开始计数），其左子节点的位置为2i+1，右子节点的位置为2i+2，而其父节点的位置为(i-1)/2。
2. 上浮操作（Sift Up）：在插入新元素时，先将新元素放置在数组的末尾，然后通过上浮操作将其移动到合适的位置，确保堆的性质（父节点大于或等于其子节点）得到维持。
3. 下沉操作（Sift Down）：当删除堆顶元素后，将数组最后一个元素放置在堆顶，并通过下沉操作将其移动到合适的位置，同样是为了维持堆的性质。

代码亮点：

1. 动态扩容机制：ensureCapacity() 方法确保当堆的大小达到数组容量时，能够自动扩展数组的大小。这样可以避免频繁的数组复制操作，提高性能。
2. 简洁的上浮和下沉逻辑：siftUp() 和 siftDown() 方法的实现非常简洁明了，易于理解和维护。通过循环和条件判断，能够高效地调整堆的结构。
3. 异常处理：在 top() 和 pop() 方法中加入了异常处理，当堆为空时抛出异常。这样可以在运行时检查堆的状态，防止程序因非法操作而崩溃。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    // 定义堆数组和当前堆的大小
    private int[] heap;
    private int size;

    // 构造函数初始化堆数组大小为0
    public Main(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 向堆中插入元素
    public void push(int value) {
        ensureCapacity(); // 确保有足够空间容纳新元素
        heap[size] = value; // 将新元素放入数组末尾
        siftUp(size++); // 调整堆，使新元素上浮到合适位置
    }

    // 返回堆顶元素（最大值）
    public int top() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty."); // 堆为空时抛出异常
        }
        return heap[0]; // 堆顶元素即数组第一个元素
    }

    // 移除并返回堆顶元素（最大值）
    public int pop() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty."); // 堆为空时抛出异常
        }
        int root = heap[0]; // 记录堆顶元素
        heap[0] = heap[--size]; // 将数组最后一个元素放到堆顶
        siftDown(0); // 调整堆，使新堆顶元素下沉到合适位置
        return root; // 返回原先的堆顶元素
    }

    // 确保数组有足够的空间存放更多元素
    private void ensureCapacity() {
        if (size == heap.length) { // 当前大小等于数组长度时
            int newCapacity = heap.length * 2; // 新容量为原容量的两倍
            heap = Arrays.copyOf(heap, newCapacity); // 创建新数组并复制旧数组内容
        }
    }

    // 上浮操作，确保新插入的元素能正确排序
    private void siftUp(int index) {
        while (index > 0 && heap[(index - 1) / 2] < heap[index]) { // 当前节点比父节点大时
            swap((index - 1) / 2, index); // 交换当前节点和父节点
            index = (index - 1) / 2; // 更新当前节点为父节点
        }
    }

    // 下沉操作，确保替换堆顶元素后能正确排序
    private void siftDown(int index) {
        int half = size >>> 1; // 计算一半的大小
        while (index < half) { // 当前节点还有子节点时
            int child = (index << 1) + 1; // 左子节点的索引
            int swapIndex = child + (heap[child] < heap[child + 1] && child + 1 < size ? 1 : 0); // 找到较大子节点的索引
            if (heap[index] >= heap[swapIndex]) { // 当前节点大于等于较大子节点时，不需要交换
                break;
            }
            swap(index, swapIndex); // 交换当前节点和较大子节点
            index = swapIndex; // 更新当前节点为较大子节点
        }
    }

    // 交换两个指定索引处的元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 初始化堆
        Main heap = new Main(100000);

        // 读取输入的操作数量
        int n = sc.nextInt();

        // 创建ArrayList存储所有输入的操作
        ArrayList<String> operations = new ArrayList<>();
        while (sc.hasNextLine() && operations.size() <= n) {
            String operation = sc.nextLine();
            operations.add(operation);
        }


        // 遍历所有操作并执行相应的方法
        for (String op : operations) {
            if (op.startsWith("push")) {
                String[] parts = op.split(" ");
                int value = Integer.parseInt(parts[1]);
                heap.push(value);
            } else if ("top".equals(op)) {
                try {
                    System.out.println(heap.top());
                } catch (IllegalStateException e) {
                    System.out.println("empty");
                }
            } else if ("pop".equals(op)) {
                try {
                    System.out.println(heap.pop());
                } catch (IllegalStateException e) {
                    System.out.println("empty");
                }
            }
        }
    }
}