堆排序与 TopK 问题实战解析

前言

在理解了堆的基础概念并实现基本结构后，我们来看两个核心应用场景：高效的堆排序算法和解决海量数据筛选的 TopK 问题。

一、建堆基础

建堆是将无序数组转化为符合堆规则的完全二叉树的过程。这是堆排序和 TopK 等所有应用的前提。相比于逐个插入元素（向上调整），基于数组原地实现的向下调整建堆，空间复杂度仅为 O(1)，且效率更高。

1.1 向上调整算法回顾

场景： 假设已有一个小堆，现在要插入一个新元素并保持堆结构。

思路： 新元素插入堆尾后，如果它比父节点更小（小堆性质），就需要'上浮'交换，直到满足堆序或到达根节点。

示例分析： 假设原小堆为 [15, 18, 19, 25, 28, 34, 65, 49, 27, 37]，size=10。插入元素 10 到索引 10 处。

1. 计算父节点索引：parent = (child - 1) / 2，即索引 4，值为 28。
2. 比较 arr[child] (10) 与 arr[parent] (28)。10 < 28，不满足小堆，交换。
3. 更新 child 和 parent 索引，继续向上比较，直到满足条件或到达根。

void AdjustUp(HPDataType* a, int child) {
    // 已知孩子节点的下标为 child，父亲节点下标为 (child-1)/2
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] < a[parent]) {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

若构建大堆，只需将比较符号反转（< 变为 >）。

1.2 利用向上调整建堆

通过循环调用 AdjustUp，对数组中每个元素进行向上调整，即可完成建堆。但这种方法的时间复杂度是 O(N log N)，因为每个节点都可能上浮到根。

1.3 向下调整算法回顾

场景： 假设堆顶元素被替换为一个更大的值（破坏小堆性质），需要修复。

思路： 当父节点位置不合适时，让父节点'下沉'。找到左右孩子中较小的一个（小堆），如果父节点比它大，则交换，继续向下调整，直到到达叶节点或满足堆序。

关键点： 判断是否到达叶节点，只需检查子节点索引是否在有效范围内。

void AdjustDown(HPDataType* 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;
        }
    }
}

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);
}

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