数据结构：堆的实现与应用

4.4.1 向下调整法

4.5 取堆顶

5. 向上调整法和向下调整法比较

推导时间复杂度，由于用图表示有些难度，这里直接用文字说明。

这是向下调整法的推导过程：

向下调整建堆的时间复杂度如图。

下面是向上调整建堆的时间复杂度推导：

总结：向上调整算法建堆是优于向下调整建堆的。

6. 堆的应用

6.1 TOP-K 问题

这种问题通常是在较大的数据样本中取出其中的最值，这时就可以通过堆来完成。

通常这类问题样本较大，排序不太可取，可以建堆来实现。

6.2 TOP-K 思路

6.2.1 用前 n 个数据来建堆

• 求最大的前 n 个就建小堆
• 求最小的前 n 个就建大堆

6.2.2 剩下的 N-K

用剩下的 N-K 个数据来和堆顶数据比较，不满足就替换堆顶元素。

6.3 示例

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

void test() {
    HP hp;
    HPInit(&hp);
    HPPush(&hp, 2);
    HPPush(&hp, 4);
    HPPush(&hp, 1);
    HPPush(&hp, 1);
    printf("%d", HPTop(&hp));
}

void CreateNDate() {
    int n = 10000;
    srand(time(0));
    const char* file = "data.txt";
    FILE* fin = fopen(file, "w");
    if (fin == NULL) {
        perror("fopen fail");
        return;
    }
    for (int i = 0; i < n; i++) {
        int x = (rand() + i) % 1000000;
        fprintf(fin, "%d\n", x);
    }
    fclose(fin);
}

void topk() {
    int k = 0;
    printf("输入 k 的值\n");
    scanf("%d", &k);
    const char* file = "data.txt";
    FILE* fout = fopen(file, "r");
    int* arr = (int*)malloc(sizeof(int) * k);
    for (int i = 0; i < k; i++) {
        fscanf(fout, "%d", &arr[i]);
    }
    // 建堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(arr, i, k);
    }
    int x = 0;
    while (fscanf(fout, "%d", &x) != EOF) {
        if (x > arr[0]) {
            arr[0] = x;
            AdjustDown(arr, 0, k);
        }
    }
    for (int i = 0; i < k; i++) {
        printf("%d ", arr[i]);
    }
    fclose(fout);
}

int main() {
    CreateNDate();
    topk();
    return 0;
}