C++数组转最大/最小堆算法困惑及代码正确性排查请求

你的实现中的核心问题 #

• 子节点存在性未判断：处理靠近数组末尾的父节点时，右子节点可能超出数组范围（比如你的例子中i=3时，右子节点索引为7，但数组最大索引是6），直接访问会导致越界。
• 比较逻辑不完整：当前代码仅在父节点同时小于左右子节点时才处理，但如果父节点只小于左或只小于右子节点，也需要交换以维持最大堆性质。
• 交换条件错误：代码中if (lc > rc)是比较子节点的索引而非值，应该比较两个子节点的元素大小，选择更大的那个与父节点交换。
• 缺少递归/迭代调整：父节点与子节点交换后，子节点所在的子树可能不再满足堆性质，需要继续向下调整该子树，直到它成为堆。
• 索引6的疑问：索引6是叶子节点，叶子节点没有子节点，本身就符合堆的要求，所以不需要处理。堆构建只需要从最后一个非叶子节点（1-based下是n/2）开始倒序处理到根节点即可。

修正后的最大堆实现代码 #

先实现heapify函数（用于调整单个节点及其子树为最大堆），再实现buildHeap函数：

#include <iostream>
#include <algorithm>
using namespace std;

// 调整以i为根的子树为最大堆（1-based索引）
void heapify(int arr[], int n, int i, int& swaps, int& comps) {
    int largest = i; // 初始化最大元素为父节点
    int lc = 2 * i; // 左子节点索引
    int rc = 2 * i + 1; // 右子节点索引

    // 如果左子节点存在且大于当前最大元素
    if (lc <= n && arr[lc] > arr[largest]) {
        comps++;
        largest = lc;
    }

    // 如果右子节点存在且大于当前最大元素
    if (rc <= n && arr[rc] > arr[largest]) {
        comps++;
        largest = rc;
    }

    // 如果最大元素不是父节点，则交换并继续调整子树
    if (largest != i) {
        swap(arr[i], arr[largest]);
        swaps++;
        heapify(arr, n, largest, swaps, comps);
    }
}

// 构建最大堆（1-based索引）
void buildMaxHeap(int arr[], int n) {
    int swaps = 0;
    int comps = 0;

    // 从最后一个非叶子节点开始倒序遍历到根节点
    for (int i = n / 2; i >= 1; i--) {
        heapify(arr, n, i, swaps, comps);
    }

    cout << "Total swaps: " << swaps << endl;
    cout << "Total comparisons: " << comps << endl;
}

// 测试示例
int main() {
    // 你的示例数组，索引0未使用（1-based），有效元素长度n=6
    int arr[] = {0, 5, 6, 8, 1, 9, 2};
    int n = 6;

    buildMaxHeap(arr, n);

    // 输出构建后的最大堆
    cout << "构建后的最大堆（1-based）：";
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

最小堆的实现（仅修改heapify的比较逻辑） #

将heapify中的比较条件改为寻找最小元素即可：

// 调整以i为根的子树为最小堆（1-based索引）
void minHeapify(int arr[], int n, int i, int& swaps, int& comps) {
    int smallest = i;
    int lc = 2 * i;
    int rc = 2 * i + 1;

    if (lc <= n && arr[lc] < arr[smallest]) {
        comps++;
        smallest = lc;
    }

    if (rc <= n && arr[rc] < arr[smallest]) {
        comps++;
        smallest = rc;
    }

    if (smallest != i) {
        swap(arr[i], arr[smallest]);
        swaps++;
        minHeapify(arr, n, smallest, swaps, comps);
    }
}

// 构建最小堆
void buildMinHeap(int arr[], int n) {
    int swaps = 0;
    int comps = 0;

    for (int i = n / 2; i >= 1; i--) {
        minHeapify(arr, n, i, swaps, comps);
    }

    cout << "Total swaps: " << swaps << endl;
    cout << "Total comparisons: " << comps << endl;
}

关键说明 #

• 1-based索引下，最后一个非叶子节点的索引是n/2（整数除法），因为对于索引i的节点，其左子节点是2i，当i > n/2时，2i会大于n，说明是叶子节点。
• 叶子节点无需处理，它们没有子节点，天然满足堆的性质。
• heapify是堆构建的核心，它确保当前节点及其子树符合堆规则，交换后递归调整子树是为了修复可能被破坏的堆结构。

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