1. 树的概念及结构
💕 概念：
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 有一个
特殊的结点，称为根结点，根节点没有前驱结点- 除根节点外，
其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。- 因此，
树是递归定义的。
1.1 树的相关概念
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为堂兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林
1.2 树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
2. 二叉树的概念及其结构
2.1 二叉树的概念
💕 概念：
一棵二叉树是结点的一个有限集合，该集合: 或者为空/由一个根节点加上两棵别称为左子树和右子树的二叉树组成
💖 注意：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
2.2 特殊的二叉树
🐶 满二叉树：
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
🐱 完全叉树：
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是
满二叉树是一种特殊的完全二叉树。
2.3 二叉树的性质
- 若规定根节点的层数为
1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点. - 若规定根节点的层数为
1，则深度为h的二叉树的最大结点数是2^h-1 - 对任何一棵二叉树, 如果度为0其叶结点个数为
n0, 度为2的分支结点个数为n2,则有n0＝n2＋1 - 若规定根节点的层数为
1，具有n个结点的满二叉树的深度h=log(n+1),(ps：h=log(n+1)是log以2为底，n+1为对数)。 - 对于具有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则无右孩子
2.4 二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1. 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2. 链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
3. 堆
3.1 堆的概念及结构
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
其实任何一个数组都可以看做一颗完全二叉树，但不一定是堆，其孩子和父亲的下标关系为：
-
leftchild=parent*2+1 -
rightchild=parent*2+2 -
parent=(child-1)/2
💕 堆的性质：
-
堆中某个节点的值总是不大于或不小于其父节点的值；
-
堆总是一棵
完全二叉树。
3.2 堆的实现
3.2.1 堆的创建
这里我们先定义一个表示堆的顺序表来进行存储堆中的数据
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
}HP;
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};
在这里我们使用的是向上调整算法，从下至上依次调整，最后保证这棵二叉树的每一个子树都是一个堆。
3.2.2 堆的插入
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->capacity == php->size) {
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (!tmp) {
perror("realloc fail::");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size++] = x;
//向上调整算法
AjustUp(php->a, php->size - 1);
}
如果第一次插入数据，我们就要先先开辟一块空间并且并将结构体中的指针指向这块空间，并将数据插入数组中，我们需要注意的是我们需要在每次插入一个数据后都进行一次向上调整，这样才能保证我们最终构建出来的二叉树是一个堆，下面我们来看一下向上调整算法。
3.2.3 堆的向上调整算法
//向上调整算法/*小堆*/
void AjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])//a[child] > a[parent]为建大堆
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
这里我们以小堆的构建为例，我们从堆中的最后一个孩子开始调整，若孩子小于父亲，则将孩子和父亲中的元素交换，交换完成后并将父亲的下标赋给孩子，使得父亲成为新的孩子，并利用这个孩子的下标找到新的父亲的下标，以此循环，直到孩子的下标变为0或者孩子小于父亲为止停止循环，由于我们每次插入一个节点时都要进行向上调整，所以最后将节点全部插入后也就会构成一个小堆了。如果我们建大堆的话只需要将if语句中的判断条件改一下即可。
3.2.4 堆的删除
//堆的删除
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
//向下调整算法
AdjustDown(php->a, php->size, 0);
}
堆的删除指的并不是删除堆中任意的数据，而是删除堆顶数据后保证他依然是一个堆,但我们如果要是直接将堆顶的数据删除时，就会改变他原来的结构，如图所示：
这时的二叉树结构已经不是一个堆了，如果我们再次从最后一个元素往上调整的话效率将会变得非常差，所以这里我们来一种巧妙的方法：将堆的堆顶元素和最后一个元素进行交换，在将最后一个元素删除，最后将堆顶的元素向下调整使他再次变成一个堆，下面我们来看一下向下调整算法。
3.2.5 堆的向下调整算法
//向下调整算法(大堆)
void AdjustDown(HPDataType* a,int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child+1<n && a[child + 1] > a[child]) {
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
将堆顶和堆的最后一个元素交换后将最后一个元素删除，然后我们就可以从堆顶开始向下调整了，这里我们需要将删除元素后的堆中的元素个数传入函数中来控制循环的结束，从堆顶开始，如果父亲小于左右孩子中大的那个孩子，就将父亲和此孩子交换，然后再将此孩子的下标作为新的父亲，然后算出新的父亲的左孩子的下标，这里我们需要先算出左孩子的下标，如果右孩子大于左孩子，就将左孩子的下标加一，再次进行父亲和孩子比较，如果父亲大于等于孩子或者孩子的下标已经超出了元素个数，则停止循环，此时的堆已经构建成了一个大堆。
3.2.6 建堆的时间复杂度
💕 向上调整建堆时间复杂度
这里我们以满二叉树来举例，如果这颗树深度非常深的话，假设这颗树高为h，最后一层的节点个数比前n-1层的节点个数都多。最后一层节点个数为2^ (h-1)个，每个节点都需要向上调整h-1次，所以最后一层需要调整 2^(h-1)*(h-1)次，化简得2^h*(h-1)/2，又因为在满二叉树中树的高度和节点之间的关系为2^h-1=N,h=log(N+1)，所以经过调整后最后一层节点所需要调整的次数变成了(N+1)*(log(N+1)-1)/2，只保留最高阶项后就是O(N*logN)了。
void UpHeapBuild(int* a, int n)
{
//向上调整建堆
for (int i = n - 1; i > 0; i--) {
AjustUp(a, i);
}
}
💕 向下调整建堆时间复杂度
在这里我们可以得出向下调整建堆的时间复杂度是O(N)，向下调整建堆的效率更高，所以我们建堆的时候强烈推荐使用向下建堆。
void DownHeapBuild(int* a, int n)
{
//向下调整建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
}
3.3 堆的完整代码
Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
//堆的销毁
void HeapDestroy(HP* php);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的打印
void HeapPrint(HP* php);
//向上调整算法
void AjustUp(HPDataType* a, int child);
//堆的删除
void HeapPop(HP* php);
//向下调整算法
void AdjustDown(HPDataType* a,int n, int parent);
//取堆顶的数据
HPDataType HeapTop(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//堆的判空
bool HeapEmpty(HP* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//堆的初始化
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
//堆的销毁
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
//堆的打印
void HeapPrint(HP* php)
{
assert(php);
for (int i = 0; i < php->size; i++) {
printf("%d ", php->a[i]);
}
printf("\n");
}
//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
向上调整算法(大堆)
//void AjustUp(HPDataType* a, int child)
//{
// 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;
// }
// }
//}
/*小堆*/
void AjustUp(HPDataType* a, int child)
{
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;
}
}
}
//堆的插入
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->capacity == php->size) {
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (!tmp) {
perror("realloc fail::");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size++] = x;
//向上调整算法
AjustUp(php->a, php->size - 1);
}
//向下调整算法(大堆)
void AdjustDown(HPDataType* a,int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child+1<n && a[child + 1] > a[child]) {
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
/*小堆*/
//void AdjustDown(HPDataType* a, int n, int parent)
//{
// int child = parent * 2 + 1;
// while (child < n)
// {
// if (child + 1 < n && a[child + 1] < a[child]) {
// child++;
// }
// if (a[parent] > a[child])
// {
// Swap(&a[parent], &a[child]);
// parent = child;
// child = parent * 2 + 1;
// }
// else
// {
// break;
// }
// }
//}
//堆的删除
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
//向下调整算法
AdjustDown(php->a, php->size, 0);
}
//取堆顶的数据
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
// 堆的数据个数
int HeapSize(HP* php)
{
assert(php);
assert(php->size > 0);
return php->size;
}
//堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void TestHeap1()
{
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
HP hp;
HeapInit(&hp);
for (int i = 0; i < sizeof(array) / sizeof(int); i++)
{
HeapPush(&hp, array[i]);
}
HeapPrint(&hp);
HeapPop(&hp);
HeapPrint(&hp);
HeapDestroy(&hp);
}
int main()
{
TestHeap1();
return 0;
}
4. 堆的应用
4.1 堆排序
💕 堆排序即利用堆的思想来进行排序，总共分为两个步骤：
建堆：
升序：建大堆
降序：建小堆
这里我们来看一下为什么升序要建大堆，降序要建小堆：
我们将堆顶的数据和最后一个孩子交换后最后一个孩子就变成了最大的数据，此时我们将堆顶的数据进行向下调整使他再次变成一个大堆，这里我们调整的时候需要将数据的总个数减去1，这样做是因为最后一个数据已经是最大的了，我们在进行下一次向下调整时就不能调整最后一个元素了，就这样当我们将每一次调整后的堆的堆顶和最后一个孩子进行交换并调整，最终数据从后往前就会排列成依次减小的顺序，所以从前往后读他就是升序的顺序了。当然，如果要是降序的话则需要建大堆后再这样操作了。
💕 堆排序的时间复杂度
首先我们使用向下调整算法建堆的时间复杂度为O(N)，然后在每一次交换并向下调整的过程时间复杂度为log(N)，以最后一层为例，最后一层又需要调整N次，所以时间复杂度就为N+N*logN，保留最高阶项，堆排序的时间复杂度为N*logN。
💕 代码实现
//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整算法(大堆)
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child]) {
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序(升序)——建大堆
void HeapsortRise(int* a, int n)
{
//先建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//排序
int size = n - 1;
while (size > 0)
{
Swap(&a[0], &a[size]);
AdjustDown(a, size, 0);
size--;
}
}
//打印数组内容函数
void ArrayPrint(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
int n = sizeof(array) / sizeof(array[0]);
HeapsortRise(array, n);
ArrayPrint(array, n);
return 0;
}
4.2 TopK问题
首先我们先来介绍一下什么是TopK问题：
所谓的TopK问题就是在一堆数据中找到前K个最大的元素或者前K个最小的元素
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
💕 思路一：
建立一个N个数的大堆，popK次，依次取堆顶数据，这里每次取堆顶数据后需要将堆顶数据删除掉，这样popK次后，我们就可以取到前K个大的数据或者前K个小的数据。这个方法的时间复杂度分析：首先建堆的时间复杂度为O(N)，然后每次pop堆顶的数据并进行向下调整的时间复杂度为O(logN)，总共popK次，时间复杂度为O(K*logN)，所以总共的。
复杂度分析：
时间复杂度为O(N+K*logN)， 空间复杂度：他们是存放在内存中的，所以为空间复杂度为O(1)。
💕 思路二：
如果数据量很大的话，那么我们的数据就不能够放到内存中，所以就只能放入磁盘中，所以第二种思路就是：建立一个K个数的小堆，依次遍历数据，遇到比堆顶数据大的就替换堆顶，再向下调整堆，最后这个小堆中就是最大的K个数。
这里我们需要注意的是如果我们要取最大的前K个数时，一开始需要建立一个K个数的小堆，一定不能建大堆，如果建大堆的话如果一开始堆顶就是最大的数，当我们遍历的时候，遇到的所有数都小于堆顶的数据，这样即使所有数都遍历过去，堆中的数据都不会发生变化，建小堆的话堆顶的数据永远是堆中所有数据中最小的，遇到一个比堆顶数据大的数据就替换堆顶的数据，并向下调整堆中的数据，这样每次调整完之后，堆顶的数据都是堆中数据最小的，就这样我们遍历完所有的数据后，堆中的数据就是前K个最大的数据了，如果要是找前K个最小的数据的话建大堆并按此操作就可以了。
复杂度分析：
时间复杂度分析：建小堆的时间复杂度是O(K)，遍历一遍除了堆中其他的数据、每一次替换堆顶数据并向下调整的时间复杂度总共是log(K)(N-K)，所以总共的时间复杂度是log(K)(N-K)+K，化简并保留最高阶项得到的时间复杂度还是O(N*logK)，空间复杂度是我们建立K个数的堆所消耗的O(K)。
代码实现：
这里我们来实现一下思路二的代码：
void TestHeap5()
{
// 造数据
int n, k;
printf("请输入n和k:>");
scanf("%d%d", &n, &k);
srand(time(0));
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}
int randK = k;
for (size_t i = 0; i < n; ++i)
{
int val = rand() % 100000;
fprintf(fin, "%d\n", val);
}
fclose(fin);
/************************************************************************/
// 找topk
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//int minHeap[5];
int* minHeap = malloc(sizeof(int)*k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &minHeap[i]);
}
// 建小堆
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(minHeap, k, i);
}
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjustDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
printf("\n");
fclose(fout);
}
int main()
{
TestHeap5();
return 0;
}
