这篇博客会完整的对于树，堆的概念，堆的应用（topk问题，堆排序）进行深度的剖析
tree.c
`#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//如何表示一个树呢（代码实现如何定义结构）
//法1.假设说明了树的度是N（最大是这么多）
struct treenode
{
int data;
struct treenode*subs[N];//这个数组是一个指针数组，里面存的都是指针，但是有缺陷，问题在于
//1.可能会存在不少空间的浪费，如假设只有一个树的度是8，其余的都是0，1，2……浪费了很多空间
//万一没有给我们树的度为多少呢，
};
//法2；
//假设我们已经定义了一个顺序表seqlist出来了，数据类型是
//typedef struct treenode* seqdata
//这个顺序表里面存的是节点的指针
//struct treenode
//{
// int data;
// seqlist s;//
//};
//法3.结构数组村粗
//struct treenode
//{
// int parenti;
// int data;
//
//};
//上面的方式各有优缺点，表示树结构的最优方法， 使用左孩子右兄弟表示法
typedef int datatype;
struct node
{
struct node*firstchild;//第一个孩子节点， 永远指向第一个孩子
struct node*pnextbrother;//指向下一个兄弟节点 指向孩子右边的兄弟
datatype data; //节点中的数据域
};
//二叉树
//不学习他的增删查改，没有意义
//而是去控制一下他的结构（高度，深度）
//作用是搜索二叉树：用来进行查找，-》平衡搜索二叉树，（avl树和红黑树，b树）（这些结构才会去学习他的增删查改）
heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//堆是一个完全二叉树
//我们已经推导了公式，已知父亲，左为父*2+1，右为父*2+2
//已知孩子，父亲为（子-1）/2
typedef int hpdata;
typedef struct heap
{
//物理结构就是一个顺序表
hpdata *a;
int size;
int capacity;
}heap;
//初始化
void heapinit(heap* hp);
// 销毁
void heapdestroy(heap* hp);
//插入
void heappush(heap *hp, hpdata x);
//删除
void heappop(heap*hp);
void adjustup(hpdata *a, int n, int child);
void heapprint(heap*hp);
//判空
bool heapempty(heap*hp);
int heapsize(heap*hp);
//
void swap(hpdata*x, hpdata*y);
//向下调
void adjustdown(int *a, int size, int parent);
heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
//初始化
void heapinit(heap* hp)
{
assert(hp);
hp->capacity =hp->size= 0;
hp->a = NULL;
}
// 销毁
void heapdestroy(heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
//向上调整
void adjustup(hpdata *a, int n, int child)//a就是这数组，n就这个数组右多大
{
assert(a);
int parent = (child - 1) / 2;
//while(parent>=0)
while (child >0)//调到根
{
if (a[child] > a[parent])//大于就交换
{
//交换
hpdata tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}
else
{
break;//小于就停止
}
}
}
//插入
//假设是大堆
void heappush(heap *hp, hpdata x)
{
assert(hp);
//满了就要先增容
if (hp->size == hp->capacity)
{
size_t newcapcity = hp->capacity == 0 ? 4 : hp->capacity * 2;
hpdata *tmp = (hpdata*)realloc(hp->a, sizeof(hpdata)*newcapcity);
if (tmp != NULL)
{
hp->a = tmp;
hp->capacity = newcapcity;
}
else
{
perror("realloc");
return;
}
}
hp->a[hp->size] = x;
hp->size++;
adjustup(hp->a, hp->size, hp->size-1);
}
void heapprint(heap*hp)
{
int i = 0;
for (i = 0; i < hp->size; i++)
{
printf("%d ", hp->a[i]);
}
}
```c
bool heapempty(heap*hp)
{
assert(hp);
return hp->size == 0;//为0就是空的，不为0就不是空的
}
int heapsize(heap*hp)
{
assert(hp);
return hp->size;
}
//向上调的时间复杂度是
//
//向上调高度次
void adjustdown(int *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[child] > a[parent])//孩子大于父亲，就交换
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//删除
//再堆里面删除不是随便任意删除什么位置都可以
//而是删除堆顶的数据（根），意义是调整堆，找到次小的值（小堆）
//向下调整，把他调整成堆，跟左右孩子中小的那个交换
//结束条件
//1.父亲<=小的那个孩子，则停止
//2.调整到叶子（当父亲走到叶子就停止，叶子是没有左孩子，左孩子下标超出数组范围就不存在）
void heappop(heap*hp)
{
assert(hp);
assert(!heapempty(hp));//空了就别删除了
//先把堆顶和底部删掉
swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;//删掉了
//交换之后，向下调整，保证不破坏堆,从0开始向下调
adjustdown(hp->a, hp->size, 0);
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
int main()
{
int a[] = {
70,56,30,25,15,10,75 };//用数组去给hp值
heap HP;//定义一个堆
heapinit(&HP);
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
heappush(&HP, a[i]);
}
heapprint(&HP);
return 0;
}
堆的应用
1.topk问题
topk问题
（就是再n个数里面找到最大的前k个，或者最小的前k个）
1.排序：我们最常见的想法就是把所有数据排一遍，然后找到其中最大的k个，但是这样假如说n非常非常大，而k却远小于n，那么就相当于杀鸡用牛刀，这种方法的最有的时间复杂度是O（n*logn）
2.我们最优的方法是是先取前k个建立一个小堆，建立小堆之后，顶部的一定是最小的，随后，n-k个入堆，与顶比较，如果比顶部的大，就交换，到最后剩下的 那k个一定就是符合要求的
// 在N个数找出最大的前K个 or 在N个数找出最小的前K个
void PrintTopK(int* a, int n, int k)
{
heap hp;
heapinit(&hp);
// 创建一个K个数的小堆
for (int i = 0; i < k; ++i)
{
heappush(&hp, a[i]);//一个一个入堆
}
// 剩下的N-K个数跟堆顶的数据比较，比他大，就替换他进堆
for (int i = k; i < n; ++i)
{
if (a[i] > heaptop(&hp))//比较，大的就入堆
{
heappop(&hp);//把顶补的删掉，
heappush(&hp, a[i]);//大的入堆
//hp.a[0] = a[i];//把顶部的换成现在大的
//adjustdown(hp.a, hp.size, 0);//向下调整
}
}
heapprint(&hp);
heapdestroy(&hp);
}
void TestTopk()
{
int n = 1000000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
// 再去设置10个比100w大的数
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[5355] = 1000000 + 3;
a[51] = 1000000 + 4;
a[15] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
int main()
{
TestTopk();
return 0;
}
2.堆排序
//堆排序
//首先先建堆，再应用堆进行排序
//升序就建大堆，降序就建小堆
void HeapSort(int* a, int n)
{
//法1.
// 直接把a构建成堆，直接控制a数组，升序，吧
//把a构建成小堆
//第一个数先看做堆，后面的数据依次加入堆，然后向上调整，构建堆,调到根就结束了，保证他还是堆
// if (n <= 1)//第一个就看成堆
// {
// return;
//}
//for (int i = 1; i < n; i++)//后面的数加入进去
//{
// AdjustUp(a,i);
//}
//法2；
//向下调整也可以，保证左子树和右子树都小堆，倒着走最后一个子树进行调整
//叶子所在的子树不需要调，所以倒着走的第一个非子节点的子树，就是最后一个节点的父亲，调完之后--，直到根
//前面的调整为后面做了铺垫，前面调整完之后一定是一个堆
for (int i = (n - 1-1) / 2; i >= 0; i--)//最后一个位置是n-1，
{
AdjustDown(a, n, i);
}
//排升序建小堆的分析：
//1.选出了最小的数放到第一个位置，如何选出次小的位置，只能从第二个位置开始，剩下的数看成一个堆，但是这样的话所有的关系都乱了，只能重新建堆才可以选出次小的堆
//我们建大堆，最大的数选出来，
//最大的数放最后一个位置，交换
//如何选出此校的 数，1.把最后一个数不看做堆里面的了，向下调整就可以选出次小的数，依次内推在重复上面过程，，原本有n个数，现在传n-1个数，就不把他当做堆里面的了
for (int end = n - 1; end > 0; end--)
{
Swap(&a[end], &a[0]);
AdjustDown(a, end, 0);//向下调整，到根部
}
}