如何实现支持自定义子节点数的Heapsort（堆排序）

核心改动点 #

• 更新heapify函数：新增d参数，遍历当前节点的所有d个子节点，找出最大值的索引，替代原二叉堆仅判断左右两个孩子的逻辑。
• 调整堆初始化的起始索引：d叉堆的最后一个非叶子节点索引为(n-2)/d（整数除法），而非二叉堆的n/2 -1。
• 递归调用传递d参数：确保递归过程中始终维护d叉堆的结构。

修改后的完整代码 #

#include <algorithm> // 依赖std::swap，也可自行实现swap逻辑

template <typename T>
void heapify(T arr[], int n, int i, int d) {
    int biggest = i;
    // 遍历当前节点的所有d个子节点
    for (int k = 0; k < d; ++k) {
        int childIndex = d * i + 1 + k;
        if (childIndex < n && arr[childIndex] > arr[biggest]) {
            biggest = childIndex;
        }
    }

    if (biggest != i) {
        std::swap(arr[i], arr[biggest]);
        // 递归调整受影响的子堆，传入d参数
        heapify(arr, n, biggest, d);
    }
}

template <typename T>
void heapsort(T arr[], int n, int d) {
    // d叉堆的最后一个非叶子节点计算方式：(n-2)/d
    for (int i = (n - 2) / d; i >= 0; --i) {
        heapify(arr, n, i, d);
    }

    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        // 调整剩余元素为d叉堆，传入d参数
        heapify(arr, i, 0, d);
    }
}

关键逻辑说明 #

1. 子节点索引计算：对于节点i，它的第k个孩子（k从0到d-1）的索引为d*i +1 +k，对应d叉堆从左到右的子节点顺序。比如d=3时，节点0的孩子是1、2、3，节点1的孩子是4、5、6，以此类推。
2. 非叶子节点起始位置：最后一个节点的索引是n-1，它的父节点索引为((n-1)-1)/d = (n-2)/d（整数除法自动向下取整），从这个节点开始向前遍历，完成堆的初始化。
3. 边界检查：遍历子节点时必须判断childIndex < n，避免数组越界访问。

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