基于数组实现最大堆：动态扩容问题及错误排查

核心问题 #

你的最大堆实现存在以下关键问题：

• 未跟踪堆的实际元素数量：仅依赖数组长度，无法区分数组中已使用的元素和未初始化的空间。
• 插入逻辑错误：每次插入都覆盖数组第一个元素，而非添加到堆的末尾。
• 未正确扩容：没有在元素数量达到数组容量时动态扩展数组。
• 冒泡逻辑无效：初始时数组长度为1，current 始终为0，循环无法执行，无法维护堆的性质。

修复后的代码 #

import java.util.Arrays;

public class Heaps {
    private int[] heap;
    private int size; // 跟踪堆中实际元素的数量

    public Heaps() {
        this.heap = new int[1];
        this.size = 0;
    }

    public int[] getHeap() {
        // 返回仅包含有效元素的数组，避免多余的0
        return Arrays.copyOf(heap, size);
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    private int parent(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 value) {
        // 当数组容量不足时扩容（通常扩容为原大小的2倍）
        if (size == heap.length) {
            heap = Arrays.copyOf(heap, heap.length * 2);
        }
        // 将新元素添加到堆的末尾
        heap[size] = value;
        int current = size;
        size++;
        // 向上冒泡，维护最大堆性质
        while (current > 0 && heap[current] > heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public static void main(String[] args) {
        int[] A = {99, 61, 58, 18, 27, 55, 72};
        Heaps hp = new Heaps();

        for (int num : A) {
            hp.insert(num);
        }

        System.out.println(Arrays.toString(hp.getHeap()));
    }
}

关键修复点 #

1. 添加size变量：准确记录堆中已存储的元素数量，区分数组容量和实际元素数。
2. 动态扩容：当size等于数组长度时，使用Arrays.copyOf将数组容量翻倍，确保有空间插入新元素。
3. 正确插入元素：将新元素放在数组的size位置（堆的末尾），然后递增size。
4. 有效冒泡逻辑：从新元素的位置开始，与父节点比较并交换，直到满足最大堆性质或到达根节点。
5. 修正返回值：getHeap返回仅包含有效元素的数组，避免返回未使用的空间（多余的0）。

运行修复后的代码，输出将符合预期：[99, 61, 72, 18, 27, 55, 58]。

内容的提问来源于stack exchange，提问作者Yashawant Sawant