堆排序与 TopK 问题实战解析

1.4 利用向下调整建堆（推荐）

向下调整建堆利用了完全二叉树的特性：叶子节点天然满足堆性质。因此，只需从最后一个非叶子节点开始，向前遍历至根节点，依次进行向下调整。这是一种局部到整体的思维。

时间复杂度： 虽然单次调整最坏是 O(log N)，但由于大部分节点靠近底部，总复杂度可证明为 O(N)，优于向上调整的 O(N log N)。

void HeapBuild(int* a, int size) {
    for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, size, i);
    }
}

二、堆排序

堆排序的核心价值在于高效维护最大值或最小值。本质是将无序数组通过堆转化为有序序列。

核心步骤：

1. 建堆： 将无序数组转化为大堆或小堆。
2. 反复取堆顶 + 修复： 将堆顶元素（极值）与末尾元素交换，缩小未排序区域，重新调整堆。

2.1 升序排序：建大堆

为什么升序要建大堆？因为大堆的堆顶是当前最大值。我们将最大值交换到数组末尾，固定下来，然后缩小范围继续调整。这样最终数组就是从小到大的顺序。

流程：

1. 建立初始大堆。
2. 交换堆顶（最大）与堆尾元素。
3. 堆顶元素破坏了大堆性质，执行向下调整。
4. 重复上述过程，直到只剩一个元素。

#include<stdio.h>

void Swap(int* a, int* b) {
    int tmp = *a; *a = *b; *b = tmp;
}

// 向下调整（大堆）
void maxHeapify(int* arr, int size, int parent) {
    int child = parent * 2 + 1;
    while (child < size) {
        if (child + 1 < size && arr[child + 1] > arr[child]) {
            child++;
        }
        if (arr[child] > arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSort(int *a, int size) {
    // 1. 建大堆
    for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
        maxHeapify(a, size, i);
    }
    
    // 2. 交换并调整
    int end = size - 1;
    while (end > 0) {
        Swap(&a[0], &a[end]);
        maxHeapify(a, end, 0); // 注意这里 size 变为 end
        end--;
    }
}

void testHeapSort() {
    int a[] = { 4, 2, 8, 1, 5, 6, 9, 7 };
    int size = sizeof(a) / sizeof(a[0]);
    printf("排序前：\n");
    for (int i = 0; i < size; i++) printf("%d ", a[i]);
    
    HeapSort(a, size);
    
    printf("\n排序后：\n");
    for (int i = 0; i < size; i++) printf("%d ", a[i]);
}

2.2 降序排序：建小堆

同理，若要降序排列，则建立小堆。每次取出堆顶最小值放到数组末尾，剩余部分继续调整为小堆。

三、TopK 问题

TopK 问题是经典场景：从海量数据（N 个元素）中找出前 K 个最大或最小的元素。

方案对比：

1. 全量排序： 将所有数据存储进内存排序。若数据量极大（如 10 亿整数），内存消耗巨大（约 4GB+），甚至无法加载。
2. 堆优化法： 只维护一个大小为 K 的堆。

具体做法（找前 K 大）：

1. 先读取前 K 个数据，建立一个小堆（堆顶是最小值）。
2. 遍历剩余 N-K 个数据：
   • 如果当前数据比堆顶大，说明它更有资格进入前 K 名，替换堆顶。
   • 替换后，对堆顶执行向下调整，维持小堆性质。
3. 遍历结束后，堆中的 K 个元素即为最大的 K 个数。

优势： 空间复杂度仅为 O(K)，无需存储全部数据，非常适合处理海量流式数据。

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
#include <time.h>
#include <stdlib.h>

const int N = 10000;

void swap(int* x, int* y) {
    int tmp = *x; *x = *y; *y = tmp;
}

// 向下调整（小堆）
void AdjustDown(int* a, int size, int parent) {
    int child = parent * 2 + 1;
    while (child < size) {
        if (child + 1 < size && a[child] > a[child + 1]) {
            child++;
        }
        if (a[child] < a[parent]) {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// 从 N 个数中选出 K 个最大的数
void TopK(int *a, int k) {
    int* kheap = malloc(sizeof(int) * k);
    if (!kheap) return;

    // 1. 读入前 K 个数据建小堆
    for (int i = 0; i < k; i++) {
        kheap[i] = a[i];
    }
    for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(kheap, k, i);
    }

    // 2. 比较剩余数据
    for (int i = k; i < N; i++) {
        if (kheap[0] < a[i]) {
            kheap[0] = a[i];
            AdjustDown(kheap, k, 0);
        }
    }

    printf("最大的 %d 个数为：", k);
    for (int i = 0; i < k; i++) {
        printf("%d ", kheap[i]);
    }
    free(kheap);
}

void testTopK() {
    int k = 10;
    int* arr = malloc(sizeof(int) * N);
    srand((unsigned int)time(NULL));
    for (int i = 0; i < N; i++) {
        arr[i] = rand() % 10000 + i;
    }
    // 模拟几个超大值
    arr[10] = 1000000 + 1;
    arr[11] = 1000000 + 2;
    // ... 省略后续赋值
    
    TopK(arr, k);
    free(arr);
}

通过这种方式，我们可以在有限的内存资源下，高效地解决海量数据的筛选问题。