大根堆的概念
大根堆是一种特殊的完全二叉树结构，其中每个节点的值都大于或等于其子节点的值。在数组表示的堆中，对于任意节点i（从0开始计数），其左子节点的位置为2i+1，右子节点的位置为2i+2，而其父节点的位置为(i-1)/2。
大根堆的操作
- Push（插入）：向堆中添加一个新的元素。
- Top（获取最大值）：返回堆顶的元素，也就是当前堆中的最大值。
- Pop（删除最大值）：移除堆顶的元素，并返回该值。
如何插入元素（Push）
当向堆中插入一个新元素时，我们首先将该元素添加到数组的末尾，然后执行上浮操作（Sift Up）。上浮操作是从叶子节点向上比较并交换节点与其父节点，直到满足堆的性质为止。
如何获取最大值（Top）
由于大根堆总是把最大的元素放在数组的第一个位置（即索引为0的位置），所以我们只需要返回数组的第一个元素即可。
如何删除最大值（Pop）
删除堆顶元素时，我们先记录下堆顶元素的值，然后将数组的最后一个元素移到堆顶，接着从堆顶开始执行下沉操作（Sift Down）。下沉操作是从根节点向下比较并交换节点与其较大的子节点，直到满足堆的性质为止。
算法重点：
- 数组表示的完全二叉树：使用数组来表示堆，其中每个元素的位置都有确定的关系：对于任意节点i（从0开始计数），其左子节点的位置为2i+1，右子节点的位置为2i+2，而其父节点的位置为(i-1)/2。
- 上浮操作（Sift Up）：在插入新元素时，先将新元素放置在数组的末尾，然后通过上浮操作将其移动到合适的位置，确保堆的性质（父节点大于或等于其子节点）得到维持。
- 下沉操作（Sift Down）：当删除堆顶元素后，将数组最后一个元素放置在堆顶，并通过下沉操作将其移动到合适的位置，同样是为了维持堆的性质。
代码亮点：
- 动态扩容机制：ensureCapacity() 方法确保当堆的大小达到数组容量时，能够自动扩展数组的大小。这样可以避免频繁的数组复制操作，提高性能。
- 简洁的上浮和下沉逻辑：siftUp() 和 siftDown() 方法的实现非常简洁明了，易于理解和维护。通过循环和条件判断，能够高效地调整堆的结构。
- 异常处理：在 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");
}
}
}
}
}
京公网安备 11010502036488号