面试题：C语言堆排序在特定场景下的优化

Question

假设你在处理大量数据（例如百万级元素）时使用C语言实现堆排序，且这些数据中有大量重复元素。请阐述如何对堆排序算法进行优化以提高性能，并给出优化后的C语言代码实现思路及关键代码片段。

Answer 1

优化思路

1. 减少重复元素比较次数：对于大量重复元素，可以采用计数排序的思想对重复元素先进行预处理，统计每个元素出现的次数，然后再进行堆排序。这样在堆排序过程中，相同元素之间不需要多次比较。
2. 采用多叉堆：常规堆排序使用二叉堆，在数据量很大时，多叉堆（如4叉堆、8叉堆等）可以减少树的高度，从而减少每次调整堆时比较和交换的次数。

代码实现思路

1. 预处理重复元素：遍历数据，使用哈希表（在C语言中可以通过数组模拟简单哈希表，如果数据范围较大可以使用更复杂的哈希函数和冲突处理机制）统计每个元素出现的次数。
2. 构建多叉堆：以4叉堆为例，节点i的子节点为4i + 1, 4i + 2, 4i + 3, 4i + 4 ，父节点为 (i - 1) / 4。
3. 堆排序过程：按照多叉堆的调整规则进行堆排序，每次取出堆顶元素时，根据统计的重复次数依次输出相同元素。

关键代码片段

// 假设数据范围不大，用数组模拟哈希表统计元素出现次数
void count_elements(int arr[], int n, int count[], int max_val) {
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
}

// 4叉堆调整函数
void heapify(int arr[], int n, int i, int count[]) {
    int largest = i;
    int child1 = 4 * i + 1;
    int child2 = 4 * i + 2;
    int child3 = 4 * i + 3;
    int child4 = 4 * i + 4;

    if (child1 < n && arr[child1] > arr[largest]) {
        largest = child1;
    }
    if (child2 < n && arr[child2] > arr[largest]) {
        largest = child2;
    }
    if (child3 < n && arr[child3] > arr[largest]) {
        largest = child3;
    }
    if (child4 < n && arr[child4] > arr[largest]) {
        largest = child4;
    }

    if (largest != i) {
        // 交换元素
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 递归调整受影响的子树
        heapify(arr, n, largest, count);
    }
}

// 优化后的堆排序
void optimized_heap_sort(int arr[], int n, int max_val) {
    int *count = (int *)malloc((max_val + 1) * sizeof(int));
    memset(count, 0, (max_val + 1) * sizeof(int));

    count_elements(arr, n, count, max_val);

    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }

    // 构建4叉堆
    for (int i = (n - 2) / 4; i >= 0; i--) {
        heapify(arr, n, i, count);
    }

    // 堆排序
    for (int i = n - 1; i > 0; i--) {
        // 交换堆顶和当前未排序部分的最后一个元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 调整堆
        heapify(arr, i, 0, count);
    }

    free(count);
}