深入理解与实现最大堆的Heapify过程：常见错误与修正

public class HeapTest {
    private int[] heap = new int[100]; // 假设堆容量为100
    private int heapSize = 0;

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

    // 获取左子节点值 (此处未直接使用，但通常用于其他堆操作)
    private int getLeftChildValue(int index) {
        // 需要检查索引是否越界
        if (getLeftChildIndex(index) < heapSize) {
            return heap[getLeftChildIndex(index)];
        }
        throw new IndexOutOfBoundsException("Left child does not exist.");
    }

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

    // 获取右子节点值 (此处未直接使用)
    private int getRightChildValue(int index) {
        // 需要检查索引是否越界
        if (getRightChildIndex(index) < heapSize) {
            return heap[getRightChildIndex(index)];
        }
        throw new IndexOutOfBoundsException("Right child does not exist.");
    }

    // 获取父节点索引
    private int getParentIndex(int index) {
        // 初始实现存在问题
        return ((int) Math.ceil((index - 2) / 2));
    }

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

    // 插入元素
    public void insert(int num) {
        if (heapSize == heap.length) {
            throw new IllegalStateException("Heap is full.");
        }
        heap[heapSize] = num;
        heapSize++;
        int currentIndex = heapSize - 1; // 新插入元素的索引

        // 上浮操作的循环条件存在问题
        while (getParentIndex(currentIndex) > 0 && heap[currentIndex] > heap[getParentIndex(currentIndex)]) {
            swap(currentIndex, getParentIndex(currentIndex));
            currentIndex = getParentIndex(currentIndex);
        }
    }

    // 辅助方法：打印堆内容 (用于调试)
    public void printHeap() {
        System.out.print("[");
        for (int i = 0; i < heapSize; i++) {
            System.out.print(heap[i] + (i == heapSize - 1 ? "" : ","));
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        HeapTest heap = new HeapTest();
        heap.insert(15);
        heap.printHeap(); // 期望: [15]
        heap.insert(5);
        heap.printHeap(); // 期望: [15,5]
        heap.insert(10);
        heap.printHeap(); // 期望: [15,5,10]
        heap.insert(30);
        heap.printHeap(); // 期望: [30,15,10,5] (这里是最终期望)
    }
}

public class HeapTest {
    private int[] heap = new int[100];
    private int 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) {
        // 对于索引为0的节点，它没有父节点，此方法不应被调用或应在调用前检查index > 0
        // 对于非0索引，父节点索引为 (index - 1) / 2
        return (index - 1) / 2;
    }

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

    // 修正后的插入元素方法
    public void insert(int num) {
        if (heapSize == heap.length) {
            throw new IllegalStateException("Heap is full.");
        }
        heap[heapSize] = num;
        heapSize++;
        int currentIndex = heapSize - 1; // 新插入元素的索引

        // 修正后的上浮操作循环条件
        // 只要当前节点不是根节点（索引 > 0），并且当前节点值大于其父节点值，就进行交换
        while (currentIndex > 0 && heap[currentIndex] > heap[getParentIndex(currentIndex)]) {
            swap(currentIndex, getParentIndex(currentIndex));
            currentIndex = getParentIndex(currentIndex);
        }
    }

    // 辅助方法：打印堆内容
    public void printHeap() {
        System.out.print("[");
        for (int i = 0; i < heapSize; i++) {
            System.out.print(heap[i] + (i == heapSize - 1 ? "" : ","));
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        HeapTest heap = new HeapTest();
        System.out.println("--- 插入 15 ---");
        heap.insert(15);
        heap.printHeap(); // 期望: [15]

        System.out.println("--- 插入 5 ---");
        heap.insert(5);
        heap.printHeap(); // 期望: [15,5]

        System.out.println("--- 插入 10 ---");
        heap.insert(10);
        heap.printHeap(); // 期望: [15,5,10]

        System.out.println("--- 插入 30 ---");
        heap.insert(30);
        heap.printHeap(); // 期望: [30,15,10,5]
    }
}

--- 插入 15 ---
[15]
--- 插入 5 ---
[15,5]
--- 插入 10 ---
[15,5,10]
--- 插入 30 ---
[30,15,10,5]