数据结构实战：堆排序与 TopK 问题详解

二、堆排序原理

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

2.1 升序排序：建大顶堆

为什么升序要建大顶堆？因为大顶堆的堆顶是当前最大值。我们将堆顶元素与数组末尾元素交换，最大值就被固定到了最终位置，然后缩小堆范围重新调整。

步骤：

1. 将无序数组建成大顶堆。
2. 交换堆顶（最大值）与当前未排序区域的末尾元素。
3. 堆顶元素被破坏，需重新向下调整。
4. 重复上述过程，直到整个数组有序。

void HeapSortAsc(int* a, int size) {
    // 1. 建大顶堆
    for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
        AdjustDownMax(a, size, i); // 假设存在对应的大顶堆调整函数
    }

    int end = size - 1;
    while (end > 0) {
        Swap(&a[0], &a[end]);
        AdjustDownMax(a, end, 0); // 调整剩余部分
        end--;
    }
}

2.2 降序排序：建小顶堆

同理，若需降序排列，则构建小顶堆。每次将最小的堆顶元素交换到数组末尾，逐步确定最小值的位置。

三、TopK 问题解决方案

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

3.1 暴力法的局限

直接对所有 N 个数据排序再取前 K 个，空间和时间开销都过大。例如处理 10 亿级数据，全量排序可能导致内存溢出。

3.2 堆优化方案

针对海量数据，我们可以只维护一个大小为 K 的堆。

场景：找前 K 个最大的数

1. 先读取前 K 个数据建立一个小顶堆。
2. 遍历剩余 N-K 个数据。
3. 若当前数据大于堆顶（堆中最小的那个），则替换堆顶并向下调整。
4. 这样堆中始终保留着目前为止遇到的最大的 K 个数。

此方法空间复杂度仅为 O(K)，时间复杂度为 O(NlogK)，非常适合处理大规模数据流。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10000

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

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

// 获取前 K 个最大的数
void GetTopK(int* arr, int k) {
    int* kheap = malloc(sizeof(int) * k);
    if (!kheap) return;

    // 1. 初始化前 K 个元素
    for (int i = 0; i < k; i++) {
        kheap[i] = arr[i];
    }

    // 2. 建小顶堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
        AdjustDownMin(kheap, k, i);
    }

    // 3. 遍历剩余数据
    for (int i = k; i < N; i++) {
        if (arr[i] > kheap[0]) {
            kheap[0] = arr[i];
            AdjustDownMin(kheap, k, 0);
        }
    }

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

void TestTopK() {
    srand((unsigned int)time(NULL));
    int* arr = malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++) {
        arr[i] = rand() % 10000 + i;
    }
    // 模拟几个极大值
    arr[10] = 1000000 + 1;
    arr[11] = 1000000 + 2;
    
    GetTopK(arr, 5);
    free(arr);
}

int main() {
    TestTopK();
    return 0;
}

通过上述方法，我们既避免了全量排序的高昂代价，又保证了结果的正确性。在实际工程中，根据数据规模和内存限制选择合适的堆大小，是解决 TopK 问题的关键。