数据结构详解：树、二叉树、堆排序与 TOP-K 问题

4. 树形结构实际运用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父节点和子节点之间的关系来表示不同层级的文件和文件夹之间的关联。

二、二叉树

1. 概念与结构

在树形结构中，我们最常用的就是二叉树，一棵二叉树是节点的一个有限集合，该节点是由一个根节点加上两棵别称为左子树和右子树的二叉树组成或者为空。

从上图可以看出二叉树具备以下特点：

1. 二叉树不存在度大于 2 的节点（孩子不超过 2 个，可以是 0 个孩子，一个孩子，两个孩子）。
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

现实中的二叉树

特殊的二叉树

1. 满二叉树： 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是 2^k-1 ，则它就是满二叉树。
2. 完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。（最后一层节点的个数不一定达到最大）

二叉树的性质

根据二叉树的特点可知：

1. 若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点。
2. 若规定根结点的层数为 1，则深度为 h 的二叉树的最大结点数是 2^h-1。
3. 若规定根节点的层数为 1，具有 n 个节点的满二叉树的深度 h=log2(n+1)(log 以 2 为底，n+1 为对数)。
4. 对任何一棵二叉树，如果度为 0 其叶结点个数为 n0 , 度为 2 的分支结点个数为 n2 ,则有 n0＝n2 ＋1。
5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：
   • 若 i>0，i 位置结点的双亲序号：(i-1)/2；i=0，i 为根结点编号，无双亲结点。
   • 若 2i+1<n，左孩子序号：2i+1，2i+1>=n 否则无左孩子。
   • 若 2i+2<n，右孩子序号：2i+2，2i+2>=n 否则无右孩子。

二叉树存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序结构： 就是使用数组存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费，而在现实中使用中只有堆才会使用数组存储，需要注意的是这个里的堆和操作系统虚拟进程空间中的堆是两码事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2. 链式结构： 二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。

二叉链有两个指针指向左右孩子，不可以向上找父亲节点，但是三叉链多了个指针指向父亲节点。

三、手动模拟实现顺序二叉树——堆

堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他特性，下面是其的概念和结构解释。

定义：如果有一个关键码的集合 K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆 (或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆（在左右子树中根节点也是对应的最小 / 最大）。

小根堆：堆顶是堆中最小的节点，大根堆：堆顶是堆中最大的节点。

注意：这里大家可能疑惑堆和二叉树具体是什么关系，可以认为堆除了具有二叉树的性质还具有堆顶是最大节点/最小节点的特性。

1. 堆的结构

这里堆的定义和顺序表的定义是类似的。

typedef int HPDataType;
// 堆的结构
typedef struct Heap {
    HPDataType* arr;
    int size; // 有效数据个数
    int capacity; // 容量
} HP;

2. 初始化

和顺序表类似。

void HPInit(HP* php) {
    assert(php);
    php->arr = NULL;
    php->capacity = php->size = 0;
}

3. 销毁

void HPDestroy(HP* php) {
    assert(php);
    if (php->arr) free(php->arr);
    php->arr = NULL;
    php->capacity = php->size = 0;
}

4. 向上调整算法

是为了下一个插入数据方法做出铺垫，将插入的数据默认为孩子节点，根据二叉树的性质可知 parent=(child-1)/2，如果我们要实现的是小堆，那么：

1. 比较 child 和 parent 谁小，谁小谁往上放（交换）。
2. 然后继续让 child 往上走（child=parent 即可），结束条件是 child>0，因为 child 走到根节点后没有其父节点。

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

// 向上调整算法 前提；往有效的堆中调整
void AdjustUp(HPDataType *arr, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        // >: 大堆
        // <: 小堆
        if (arr[child] < arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

5. 插入数据

1. 初始情况下需要动态增容（这里和顺序表类似）。
2. 插入数据：php->arr[php->size] = x。
3. 判断插入的数据是否符合大堆/小堆，不符合则调用向上调整算法（这里是使用大堆）。
4. 最后让 size++。

// 插入数据
void HPPush(HP* php, HPDataType x) {
    assert(php);
    if (php->size == php->capacity) {
        int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
        // 空间满了，需要增容
        HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL) {
            perror("realloc fail!\n");
            exit(1);
        }
        php->arr = tmp;
        php->capacity = newcapacity;
    }
    php->arr[php->size] = x;
    // 向上调整
    AdjustUp(php->arr, php->size);
    ++php->size;
}

6. 判空

这里和顺序表一样。

bool HPEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}

7. 求 size

返回堆中有效的数据个数。

int HPSize(HP* php) {
    assert(php);
    return php->size;
}

8. 向下调整算法

我们已知父亲节点来找孩子节点，假设我们要实现的是小堆，那么就需要让父亲节点和孩子节点比较，这里需要注意，我们需要让左右节点均要和父亲节点比，谁小谁和 parent 交换，然后让 parent 走到 child 位置，循环进行该操作直至 child 走到 n 结束。

void AdjustDown(HPDataType* arr, int parent, int n) {
    int child = parent * 2 + 1;
    while (child < n) {
        // 先找最大的孩子，这里排序是<
        // 如果是文件的是创建大堆，所以是>
        if (child + 1 < n && arr[child] > arr[child + 1]) {
            child++;
        }
        // 先找最大的孩子，这里排序是>
        // 如果是文件的是创建大堆，所以是<
        if (arr[child] < arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

9. 删除堆顶数据

1. 首先保证堆不为空，调用堆判空接口。
2. 删除堆顶元素。

如果直接删除堆顶元素，让孩子节点均往前移动会导致原来的孩子节点变成父亲节点，左右孩子顺序不对等情况，如下图中原本 25 是 15 的左孩子，现在变成 56 的兄弟节点，那么我们就需要重新一个个调整，代价太大了，那么有没有方法可以解决？

我们交换堆顶元素和最后一个数据，然后让 size--，走到 a[5] 位置，a[5] 可以存储数据，但是不是有效的（即 10 不是堆中有序的数据），我们发现 70 变成了堆顶，但是 15 56 25 等数据之间的关系并没有发生变化，因此我们只需要让堆顶 70 向下调整，直接调用向下调整方法即可。

具体步骤如下：

1. 将堆顶元素与堆中最后一个元素进行交换。
2. 删除堆中最后一个元素。
3. 将堆顶元素向下调整到满足堆特性为止。

10. 获取堆顶数据

判空后直接返回 a[0] 位置的数据即可。

HPDataType HPTOP(HP* php) {
    assert(!HPEmpty(php));
    return php->arr[0];
}

注意：上述所说的向上调整算法和向下调整算法均有个前提是往有效的堆中调整。

五、堆排序

1. 思考

这里我们需要思考：排升序和排降序时需要建大堆还是小堆。这里第一反应是通过循环取堆顶元素发现排升序是建立小堆，降序建立大堆。那么是对还是错？？？

具体操作：

1. 创建数组。
2. 我们调用堆中的 push 接口将数组中的数据建堆。
3. 通过频繁取堆顶元素放入到数组中（条件为堆不为空），并且要不断删除堆顶。

注意：大家这里可能疑惑为什么不直接打印堆顶元素，而是将堆顶元素取出来放入数组中，首先我们明确需要的条件是将数组排序，打印堆顶元素并没有直接改变数组中原本的数据。

// 排升序----建大堆，因为调用 AdjustDown 函数，将大的放到最后一个子节点，依次这样进行，会使得最小的在根节点处，就变成升序
// 排降序----建小堆，因为调用 AdjustDown 函数，将小的放到最后一个子节点，依次这样进行，会使得最大的在根节点处，就变成降序
// 借助数据结果---堆
void test01() {
    int arr[] = {17, 20, 10, 13, 19, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    HP hp;
    HPInit(&hp);
    // 调用 push 将数组中的数据建堆
    for (int i = 0; i < n; i++) {
        HPPush(&hp, arr[i]);
    }
    int i = 0;
    while (!HPEmpty(&hp)) {
        arr[i++] = HPTOP(&hp);
        HPPop(&hp);
    }
    for (int j = 0; j < n; j++) {
        printf("%d ", arr[j]);
    }
    HPDestroy(&hp);
}

我们这里来看下我们之前学习过的冒泡排序的代码是如何的，经过比较发现冒泡排序是通过思想来实现排序，而上述的堆排序是通过使用数据结构——堆来辅助实现的，因此要实现堆排序需要借助堆的排序思想。

2. 冒泡排序：

// 冒泡排序，时间复杂度 O（n^2）
void BubbleSort(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        int exchange = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                exchange = 1;
                Swap(&arr[j], &arr[j + 1]);
            }
        }
        if (exchange == 0) {
            break;
        }
    }
}

3. 建堆——算法复杂度的优与劣

这里我们根据数组中存储的最后一个数据的有效下标（孩子节点）根据 parent=（child-1)/2 可得，依次递减 parent 直至根节点，结束循环。

大家可能疑惑在向下调整算法中可不可以从 a[0] 位置开始调整？答案是不可以，因为向上调整算法和向下调整算法成立的前提是该堆已经是有效的堆，从 a[0] 开始调整就相当于从有效的大/小堆中来调整大/小堆，所以不行，我们应该依次调整左右子树的大/小堆最后整体形成大/小堆。

注意：大家可能会把堆排序中的向上寻找 parent 节点认为是向上调整算法，但是如何确定是向上/向下调整算法的实质是调整方向，父亲节点——>子节点是向下调整，是通过比较两个孩子之间谁和父亲节点大/小来实现，可以保证堆的已有顺序不会被修改。

代码如下：

void HeapSort(int* arr, int n) {
    // 根据给定的 arr 来进行建堆
    // child:n-1 parent;(n-1-1)/2
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(arr, i, n);
    }
}

时间复杂度： 我们发现如果要建的堆是满二叉树则一共有 2^h-1 个节点，最坏情况下就是从根节点到最后一个节点一次次往下移动（一层层移动），则 h=log2(n+1), 向下调整为 logn，那么总时间复杂度为 nlogn。

那么可以使用向下调整算法建堆也是可以使用向上调整算法的，那么哪个时间复杂度更优捏？初次思考我们发现两个算法均是 nlogn，那么是不是如此呢？

向下调整算法证明： 因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 (时间复杂度本来看的就是近似值，多几个结点不影响最终结果)： 需要移动节点总的移动步数为：每层节点个数 x 向上调整次数。

从第一层到最后一层节点个数逐渐增多，向下调整次数逐渐减少。

向上调整算法时间复杂度证明： 这里和向下调整算法证明类似，最后可以得出 F(n)=(n+1)(log2(n+1)-2)+2，则时间复杂度为O(n*logn)。

结论：因此向下调整算法是堆排序中主流用法！

4. 排序

假设我们需要排降序，

1. 我们通过交换根节点 a[0] 和最后一个节点的数据。
2. 让 end--。
3. 使用向下调整算法不断将小的数据放到根节点处。

结论：根据上述步骤我们得到: 排升序----建大堆，因为不断交换堆顶数据和最后一个位置数据交换，将大的放到最后一个子节点，依次这样进行，会使得最小的在根节点处，就变成升序。 排降序----建小堆，因为不断交换堆顶数据和最后一个位置数据交换，将小的放到最后一个子节点，依次这样进行，会使得最大的在根节点处，就变成降序。

六、TOP-K 问题

TOP-K 问题：即求数据集合中前 k 个最大的元素或者最小的元素，一般情况下数据量都比较大。 比如：专业前 10 名，世界 500 强，富豪榜，游戏中前 100 的活跃玩家等。 对于 TOP-K 问题，能想到的最简单直接的方法就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中），最佳的方法就是使用堆来解决，基本思路如下：

1. 用数据集合中前 k 个元素来建堆 前 k 个最大的元素，则建小堆。 前 k 个最小的元素，则建大堆。

2. 用剩余的 N-k 个元素依次与堆顶元素进行比较，不满足则替换堆顶元素 将剩余 N-K 个元素依次与堆顶元素比较完之后，堆中剩余的 k 个元素就是所求的前 k 个最小或者最大的元素。

例子：假设我们有 N 个数据，N 是 10 亿个整数，需要申请多大的内存？

换算： int = 4 byte 1G=1024MB=10241024KB=10241024*1024 byte

根据上述换算可得：1G 约等于 10 亿个字节，因此存储 10 亿数据需要申请 4G 内存。

如果面试官问我们，如果我们只有 1G 内存——我们该如何解决？ 这里我们可以分多次来存储，建立 4 个堆，每份都求取该堆中最大的几个数据，最后四个堆中数据个数相加为 k 即可。

那么假设只有 1KB 内存该如何呢？ 先取前 k 个数据进行建堆，遍历剩下的 N-K 个数据跟堆顶数据进行比较。

找最大的前 K 个数据，建小堆，因为堆顶是该堆中最小的数据，当我们每遍历一个数据就和堆顶比谁大，谁大谁入堆（小就出堆）。

创造数据：

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

生成了 data.txt 文件，里面存放了十万个整型数据。

遍历剩余的 N-K 个数据，和堆顶比大小，符合条件则调用向下调整算法。

void TopK() {
    int k = 0;
    printf("请输入 K：");
    scanf("%d", &k);
    // 读取文件中前 k 个数据建堆
    const char* file = "data.txt";
    FILE* fout = fopen(file, "r");
    if (fout == NULL) {
        perror("fopen error");
        exit(1);
    }
    // 找最大的前 K 个数，建小堆
    int* minHeap = (int*)malloc(sizeof(int) * k);
    if (minHeap == NULL) {
        perror("malloc fail!");
        exit(2);
    }
    // 读取文件中前 K 个数据建堆
    for (int i = 0; i < k; i++) {
        fscanf(fout, "%d", &minHeap[i]);
    }
    // 建堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(minHeap, i, k);
    }
    // 遍历剩下的 n-k 个数据，跟堆顶比较，谁大谁入堆
    // 调整堆
    int x = 0;
    while (fscanf(fout, "%d", &x) != EOF) {
        if (x > minHeap[0]) {
            minHeap[0] = x;
            AdjustDown(minHeap, 0, k);
        }
    }
    for (int i = 0; i < k; i++) {
        printf("%d ", minHeap[i]);
    }
    fclose(fout);
}

打印结果：

结论：找最大的前 K 个数据，建小堆，找最小的前 K 个数据，建大堆。

总结

1. 树结构：作为非线性数据结构的基石，通过根节点与子树的层次关系，构建了自然的层级模型，体现了数据间的'长幼'逻辑。
2. 二叉树：以简洁的左右子树划分，强化了顺序的重要性，满二叉树与完全二叉树的特性为高效算法（如堆）奠定了基础。
3. 堆结构：作为二叉树的特殊形态，通过向上/向下调整算法，将层次化结构转化为排序利器，小根堆与大根堆的区分直接服务于 TOP-K 等实际问题。
4. TOP-K 问题：利用堆的层次调整能力，在大数据场景下高效求解极值问题，体现了'长幼有序'思想在资源优化中的关键作用。

全文贯穿'层次决定顺序，结构决定效率'的理念，展示了数据结构从理论到实践的完整链路。