C++手动实现Heap数据结构插入超容量时如何动态扩容？

你的报错和扩容逻辑失效是以下几个原因导致的：

• 析构函数逻辑完全错误：原析构函数先将element指针指向新分配的长度为1的数组，丢失了原有堆数组的内存地址，既产生内存泄漏，释放的也不是原本分配的内存，直接触发malloc报错。
• 数组拷贝越界：getElement()方法的入参是1-based的节点索引，你循环传入0时会访问element[-1]，属于非法内存访问。
• 缺少必要的成员方法：你调用了setElementArray()但未实现，也没有更新容量的逻辑，扩容后capacity值不变，后续判断会重复触发扩容。
• 旧数组内存未释放：扩容后原有堆数组的内存没有释放，会持续造成内存泄漏。

第一步：补充HEAP类的必要成员方法 #

在heap.h的HEAP类public区域添加以下两个方法：

void setCapacity(int newCap) {
    capacity = newCap;
}

void setElementArray(Element* newArr) {
    delete[] element; // 先释放旧数组内存
    element = newArr;
}

第二步：修正析构函数 #

修改heap.cpp中的析构函数逻辑：

HEAP::~HEAP(void) {
    delete[] element; // 直接释放构造函数分配的数组内存即可
}

第三步：修正Insert函数的扩容逻辑 #

修改后的Insert函数如下：

void Insert(HEAP &i_heap, int flag, int key)
{
    if (flag != 1 && flag != 2)
    {
        cout << "Error: invalid flag value\n";
        return;
    }
    if (flag == 2)
    {
        cout << "Before insert operation:\n";
        PrintHeap(i_heap);
    }
    Element new_element;
    new_element.key = key;

    // 修正后的扩容逻辑
    if (i_heap.getCapacity() <= i_heap.getSize())
    {
        int oldCap = i_heap.getCapacity();
        int newCap = oldCap == 0 ? 1 : oldCap * 2; // 兼容初始容量为0的边界情况
        Element *newElement = new Element[newCap];
        // 拷贝逻辑修正：getElement入参为1-based索引
        for (int i = 1; i <= i_heap.getSize(); i++)
        {
            newElement[i-1] = i_heap.getElement(i);
        }
        // 更新堆的数组指针和容量
        i_heap.setElementArray(newElement);
        i_heap.setCapacity(newCap);
    }

    InsertHelper(i_heap, new_element);

    for(int i = floor(i_heap.getSize() / 2); i >= 1 ; i--) {
        Heapify(i_heap, i);
    }

    if (flag == 2)
    {
        cout << "After insert operation:\n"; // 修正原代码的笔误
        PrintHeap(i_heap);
    }
}

额外注意事项 #

建议补充实现HEAP类的拷贝构造函数和拷贝赋值运算符，避免浅拷贝导致的重复释放问题：

// 拷贝构造函数，放在HEAP类public区域
HEAP(const HEAP& other) {
    capacity = other.capacity;
    size = other.size;
    element = new Element[capacity];
    for (int i = 0; i < size; i++) {
        element[i] = other.element[i];
    }
}

// 拷贝赋值运算符，放在HEAP类public区域
HEAP& operator=(const HEAP& other) {
    if (this != &other) {
        delete[] element;
        capacity = other.capacity;
        size = other.size;
        element = new Element[capacity];
        for (int i = 0; i < size; i++) {
            element[i] = other.element[i];
        }
    }
    return *this;
}

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