优化最大堆插入操作：修复上浮（Heapify）算法中的常见陷阱

// 原始的父节点索引计算方法
private int getParentIndex(int index) {
    return ((int) Math.ceil((index - 2)/2));
}

// 原始的插入方法中的上浮循环
private void insert(int num) {
    heap[heapSize] = num;
    heapSize++;
    int index = heapSize - 1;
    while (getParentIndex(index) > 0 && heap[index] > heap[getParentIndex(index)]) {
        swap(index, getParentIndex(index));
        index = getParentIndex(index);
    }
}

private int getParentIndex(int index) {
    // 使用整数除法，更简洁高效且正确
    return (index - 1) / 2;
}

private void insert(int num) {
    heap[heapSize] = num; // 将新元素添加到堆的末尾
    heapSize++;
    int index = heapSize - 1; // 新元素的当前索引

    // 只要当前节点不是根节点（index > 0），并且当前节点值大于其父节点值，就进行上浮
    while (index > 0 && heap[index] > heap[getParentIndex(index)]) {
        int parentIndex = getParentIndex(index); // 获取父节点索引
        swap(index, parentIndex); // 交换当前节点与父节点
        index = parentIndex; // 更新当前节点索引为原父节点索引，继续向上比较
    }
}

public class MaxHeap {
    private int[] heap;
    private int heapSize;
    private int capacity; // 堆的容量

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.heapSize = 0;
    }

    // 获取左子节点索引
    private int getLeftChildIndex(int index) {
        return (2 * index + 1);
    }

    // 获取右子节点索引
    private int getRightChildIndex(int index) {
        return (2 * index + 2);
    }

    // 获取父节点索引 (修正后)
    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    // 交换两个位置的元素
    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

    // 插入元素并进行上浮 (修正后)
    public void insert(int num) {
        if (heapSize == capacity) {
            System.out.println("Heap is full. Cannot insert " + num);
            return;
        }
        heap[heapSize] = num; // 将新元素添加到堆的末尾
        heapSize++;
        int currentIndex = heapSize - 1; // 新元素的当前索引

        // 只要当前节点不是根节点（索引 > 0），并且当前节点值大于其父节点值，就进行上浮
        while (currentIndex > 0 && heap[currentIndex] > heap[getParentIndex(currentIndex)]) {
            int parentIndex = getParentIndex(currentIndex); // 获取父节点索引
            swap(currentIndex, parentIndex); // 交换当前节点与父节点
            currentIndex = parentIndex; // 更新当前节点索引为原父节点索引，继续向上比较
        }
    }

    // 打印堆内容 (用于调试和验证)
    public void printHeap() {
        System.out.print("Heap: [");
        for (int i = 0; i < heapSize; i++) {
            System.out.print(heap[i]);
            if (i < heapSize - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(10); // 假设堆的容量为10
        heap.insert(15);
        heap.printHeap(); // Expected: [15]
        heap.insert(5);
        heap.printHeap(); // Expected: [15, 5]
        heap.insert(10);
        heap.printHeap(); // Expected: [15, 5, 10]
        heap.insert(30);
        heap.printHeap(); // Expected: [30, 15, 10, 5] (After 30 is inserted and floats up)
        heap.insert(20);
        heap.printHeap(); // Expected: [30, 20, 10, 5, 15] (After 20 is inserted and floats up)
    }
}

Heap: [15]
Heap: [15, 5]
Heap: [15, 5, 10]
Heap: [30, 15, 10, 5]
Heap: [30, 20, 10, 5, 15]