【数据结构初阶】---堆的实现、堆排序以及文件中的TopK问题

1.树的概念及结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根结点没有前驱结点，除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
结构图：
注意：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2树的相关概念

1.结点的度：一个结点含有的子树的个数称为该结点的度； 如上图：A的为6
2.叶结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等结点为叶结点
3.非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等结点为分支结点
4.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
5.孩子结点或子结点： 一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
6.兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
7.树的度：一棵树中，最大的结点的度称为树的度； 如上图：树的度为6
8.结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
9.树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
10.堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
11.结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
12.孩子结点或子结点：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
13.森林：由m（m>0）棵互不相交的树的集合称为森林；

2.二叉树的概念及结构

2.1二叉树的概念

与树不同，二叉树根结点的子节点有且不超过两个。

以下几个都是二叉树：

2.2特殊的二叉树

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

##2.3 二叉树的性质

1. 若规定根结点的层数为h，则一棵非空二叉树的第h层上最多有2^(h-1)个结点
2. 若规定根结点的层数为h，则深度为h的二叉树的最大结点数是 2^h-1
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n1, 度为2的分支结点个数为n2,则有n1=n2+1
4. 假设在顺序表中父亲节点parent的下标是i，则孩子节点child的下标分别是i * 2 + 1和i * 2 + 2，分别对应左右孩子
5. 假设在顺序表中孩子节点child的下标是i,不管其是左孩子还是有孩子，其父亲节点的下标都是(i - 1) / 2

2.4二叉树的存储形式

二叉树分为完全二叉树和不完全二叉树，对于完全二叉树，我们可以采用顺序表进行存储，对于不完全二叉树我们则需采用链式存储

3.堆的顺序结构及实现

3.1堆的概念

堆是一种特别的完全二叉树，堆分为大堆和小堆。
对于大堆，堆中任意某个节点的值总是大于其子节点的值。
对于小堆，堆中任意某个节点的值总是小于其父节点的值。

3.2堆的实现

堆结构的定义

对于堆我们是采用顺序表进行存储，因此定义了一个指向数组的指针a和存储数据个数和申请的空间大小的两个变量。

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;//数据个数int capacity;//空间大小
}HP;

堆的初始化

堆的初始化就是顺序表的初始化，我们先不申请空间，后续插入数据的时候我们再申请。

//堆的初始化
void HPInit(HP* php)
{php->a = NULL;php->size = php->capacity = 0;
}

堆的插入

我们先判断空间是否足够，当前空间大小为0的话申请4个字节大小的空间，不为空的话就进行扩容两倍。

//堆的插入
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->size == php->capacity){HPDataType newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("HPPush():realloc");return;}php->a = tmp;php->capacity = newCapacity;}//先把数据插入数组尾部php->a[php->size++] = x;//然后向上调整AdjustUp(php->a, php->size - 1);
}

向上调整这个函数传的两个参数分别表示要调整的数组和要调整的孩子节点child在数组中的下标。
有了孩子节点的下标我们就可以计算其父亲节点的下标：int parent = (child - 1) / 2;
因为我们要实现的是小堆，所以如果父亲节点比孩子节点大，我们则将父子节点进行交换，交换完后我们得到新的父子节点的下标，最坏的情况是孩子节点向上不断交换，最后孩子节点的下标==0，说明其所在位置已经是根节点了，是最小的数了，比较也就停止。

//向上比较交换
void AdjustUp(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;}//a[child] > a[parent],符合小堆逻辑，不用交换了else{break;}}
}

里面对父子节点进行交换我们也单独写一个函数，方便后续我们要使用的时候直接调用

//交换父子节点
void Swap(HPDataType* child, HPDataType* parent)
{HPDataType tmp = *child;*child = *parent;*parent = tmp;
}

堆的删除

我们要删除的是堆的根，我们怎么删除他呢？直接删除吗？不行，因为直接删除的话剩下的节点直接的关系就全乱了，假如直接删除根节点后，顺序表中的第二个数据就成为了根，而其兄弟节点成为了他的孩子，这时候二者就有了大小关系，但我们知道兄弟节点之间是没有大小关系的，因此这时候顺序表的剩下的数据还是一个堆吗？不是了，他们直接的关系全乱了。
所以我们要删除根节点的办法是先将根节点个顺序表中的最后一个数据进行交换，然后这时候删除最后一个节点就相当于删除了原本的根节点。删除完后我们就需要对这时候的根节点进行调整了。

//堆的删除，删除的是根
void HPPop(HP* php)
{assert(php);assert(php->size);//先将根和数组最后一个数据进行交换Swap(&(php->a[0]), &(php->a[php->size - 1]));//然后删除数组最后一个数据，即是删除原本小堆的根数据php->size--;//然后向下比较交换父子节点AdjustDown(php->a, php->size, 0);
}

如何调整呢？，我们传三个参数，一个是要操作的顺序表，一个是顺序表中元素的个数，因为我们前面删除了最后一个数(也就是原本的根节点)，所以我们传数据个数的时候需要减去原本的那个根节点。第三个参数是需要调整的这个节点的下标，因为我们是向下调整，需要这个节点与其孩子节点进行比较，所以我们命名这个节点为parent。
怎么比较呢？这里我们是要保持我们的堆依旧是小堆，所以我们要让大的元素与其孩子进行交换，但一般父亲节点都有两个孩子，我们要与谁进行交换呢？我们要与两个孩子中较小的那个孩子进行交换，因为如果我们是与较大的那个孩子进行交换的话，我们还记得小堆的性质：小堆中任意一个父亲节点的值都小于其孩子节点。
所以如果我们与较大的那个孩子节点交换后，这个孩子节点就成为了父亲节点，他需要比他的孩子节点小，但是他是两个孩子中大的那个呀，他成为父亲节点后，他原本的兄弟节点就成为了他的孩子，但他比他孩子大，这就不构成小堆了。所以我们要与较小的那个孩子进行比较。
我们用假设法先假设左孩子较小，如果右孩子比左孩子小，那child就变成右孩子。
后续就是如果父亲节点比孩子节点大，就交换，然后确认出新的孩子节点和父亲节点。

//向下比较交换父子节点
void AdjustDown(HPDataType* a, int n, int parent)
{//n是数据个数，parent是父亲节点的下标//假设法，先假设左孩子是比较小的那个int child = parent * 2 + 1;//当这个父亲节点变成叶子节点的时候就结束了//当他是叶子节点，那他就没孩子了，他孩子的下标就越界了while (child < n){		//如果只有左孩子，child+1最后可能越界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;}//a[parent] < a[child]满足小堆逻辑else{break;}}
}

返回堆的根

判断不为空后直接返回顺序表第一个元素即可。

//返回堆的根
HPDataType HPTop(HP* php)
{assert(php);assert(php->size);return php->a[0];
}

堆的判空

size == 0为真返回1，为假返回0

//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

堆的销毁

堆的销毁就是将顺序表动态申请的空间进行释放。

//堆的销毁
void HPDestroy(HP* php)
{free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

4.堆排序

堆排序的思路是：降序建小堆，升序建大堆。
以升序为例，我们先建大堆，建完后我们的根节点是不是就是这个堆中最大的那个元素，我们将根节点和数组中的最后一个元素进行交换，然后将除最后一个元素(被交换的那个根节点)之外剩下的元素进行向下调整再次形成一个大堆，这时候这个大堆的根节点是不是就是这个堆中最大的元素，也就是数组中第二大的元素，然后我们继续向下调整，一直这个样重复，我们就能得到一个升序的序列了。
参考代码如下：

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<assret.h>void Swap(int* child, int* parent)
{int temp = *child;*child = *parent;*parent = temp;
}//向下调整，父亲与孩子比较交换
void AdjustDown(int* a, int n, int parent)
{assert(a);//假设法，先假设左孩子是较大的那个int child = parent * 2 + 1;//孩子下标超过剩余元素个数说明父亲节点已经变成叶子节点了while (child < n){if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{assert(a);//升序建大堆//从最后一个非叶子节点开始向下调整建堆//最后一个非叶子节点的下标是(n - 1 - 1) / 2，这个下标作为父亲节点的下标for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//建堆完后，我们交换第一个和最后一个元素，然后将根元素向下调整int end = n - 1;while (end){Swap(&a[0], &a[end]);//end是最后一个元素的下标AdjustDown(a, end, 0);//end是除最后一个元素外剩余元素的个数--end;}
}int main()
{int a[] = { 9,5,6,3,7,8,1,2,0,4 };//排个升序HeapSort(a, sizeof(a) / sizeof(a[0]));for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){printf("%d ", a[i]);}return 0;
}

5.文件中的TopK问题

文件中的TopK问题就是我们有一个文件，里面有很多数据，我们要找出这些数据中最大的前k个元素。
思路是: 我们先创建一个k个元素的小堆(向下调整建堆)，这k个元素是文件中的前k个元素。因为是小堆，所以根节点位置的元素是k个元素中最小的那个元素，然后我们将文件中剩下的n-k个元素依次与根节点进行比较，如果比根节点位置的数据大，我们就将根节点的数据进行覆盖，然后我们将这个节点进行向下调整成新的小堆，这样我们确保了根节点永远是k个元素中最小的那个，这样子最后比较完后我们这个小堆中的k个元素就是文件里的n个元素中最大的k个元素了。
参考代码如下：

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<assret.h>
#include<stdlib.h>
#include<time.h>//空间复杂度:O(k)
//时间复杂度:O((N-K)*logK),即O(N)void Swap(int* child, int* parent)
{int temp = *child;*child = *parent;*parent = temp;
}//向下调整，父亲与孩子比较交换
void AdjustDown(int* a, int n, int parent)
{assert(a);//假设法，先假设左孩子是较小的那个int child = parent * 2 + 1;//孩子下标超过剩余元素个数说明父亲节点已经变成叶子节点了while (child < n){if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void CreateNData()
{int n = 100000;srand((unsigned int)time(NULL));FILE* fp = fopen("test.txt", "w");if (fp == NULL){perror("CreateNData():fopen");return;}for (int i = 0; i < n; i++){int x = rand() % 10000000;fprintf(fp, "%d\n", x);}fclose(fp);fp = NULL;
}void PrintTopK()
{printf("请输入要查找最大的前多少个数:");int k = 0;scanf("%d", &k);//为数组申请k个空间int* kminHeap = (int*)malloc(sizeof(int) * k);FILE* pf = fopen("test.txt", "r");if (pf == NULL){perror("PrintTopK():fopen");return;}//读取文件前k个数据for (int i = 0; i < k; i++){fscanf(pf, "%d", &kminHeap[i]);}//建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminHeap, k, i);}int x = 0;//返回的是读取成功的个数，读取失败返回-1while (fscanf(pf, "%d", &x) > 0){if (x > kminHeap[0]){kminHeap[0] = x;AdjustDown(kminHeap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", kminHeap[i]);}
}int main()
{//先先文件中放些数据//CreateNData();PrintTopK();return 0;
}