目录
二叉树的相关定义：
堆：
堆是啥？
堆中父子节点如何相互定位？
堆的基本结构定义：
堆的插入（涉及向上调整）：
2.堆的删除（涉及向下调整）：
建堆算法(将一组没有堆特性的数据原地修改为大、小堆)：
堆的应用：
1.堆排序(向下调整)
2，topk问题(取得一组数据中最大或最小的k个数)
堆相关的代码总览：
前言：在刚接触c语言的函数时我们就学过或者了解过递归，但递归的层数过多会有栈溢出的风险，因此在做题时能用循环就用循环，以至于我们中的多数人都递归不熟悉。于是，二叉树就是助咱加深理解递归的救星——因为二叉树就是递归定义的，
二叉树的相关定义：
二叉树由一个一个节点构成，基本单位是根、左子树和右子树，节点间的基本关系是父节点和子结点(父和子是相对的)，如下图：
- 没有节点的树称为空树
- 对于有节点的树，有两个特殊情况---完全二叉树和满二叉树
相关特殊名词：
- 没有父节点(最顶层)的节点叫做根节点
- 没有分支节点的节点叫做叶子节点
- 一个节点所具有的分支节点(子节点)数叫做度
- 二叉树的层数叫做深度
二叉树的相关特性：
- 同一层的节点间没有父子关系
- 一个节点至多有两个分支节点（子节点）
堆：
堆是啥？
堆就是前面介绍过的完全二叉树——前h-1层满节点，第h层从左往右节点不间断，这样的二叉树用数组存储的话父节点和子节点可以方便的互相通过下标来定位，兼备了二叉树逻辑的巧妙和数组随机访问的高效。
注意：
- 尽管堆用数组来管理数据，我们在后续的一系列操作中还是尽量把堆当成完全二叉树来看，只不过可以利用数组随机访问的特性来进行父子节点间的相互访问
- 堆要求父亲节点总是大于或小于孩子节点——父亲大于孩子就是大堆，“谁大谁当爹”；父亲小于孩子就是小堆，“谁小谁当爹”。
堆中父子节点如何相互定位？
堆的基本结构定义：
堆的底层使用数组实现，所以可以像顺序表那样定义结构，如下
typedef int datatype;
typedef struct binary
{datatype* arr;int size;int capacity;
}binary;-
堆的插入（涉及向上调整）：
堆的插入大体分为两步：
- 一是在尾部添加数据(代码和顺序表的尾插一样)
- 二是对新插入的数据进行向下调整（因为新增数据的大小不确定，需要自下而上进行调整）
由于向下调整算法本质上是可以脱离堆来单独对一组存在数组里的数据使用的(当然，还是要使用堆的下标特性)，所以在向下调整的参数里没有结构体对象，而是数组。
//交换值
void Swap(datatype* val1,datatype* val2)
{datatype tmp = *val1;*val1 = *val2;*val2 = tmp;
}
//向上调整算法
void Adjust_up(datatype* arr, int size)
{int child = size - 1;int father = (size - 1) / 2;while (child > 0){if (arr[child] < arr[father]) //'<' 是维持小堆的逻辑，改成 '>'则是维持大堆{Swap(&arr[child], &arr[father]); }child = father;father = (child - 1) / 2;}
}
//尾部插入
void PushBinary(binary* bnode,datatype val)
{
//扩容逻辑if (bnode->size == bnode->capacity){int newcapacity = bnode->capacity == 0 ? 4 : 2 * bnode->capacity;datatype* newarr = (datatype*)realloc(bnode->arr, newcapacity*sizeof(int));if (newarr == NULL){perror("realloc fail");exit(1);}bnode->capacity = newcapacity;bnode->arr = newarr;}
//插入新数据bnode->arr[bnode->size] = val;++bnode->size;
//上面定义过的向上调整算法，从新插入的元素开始进行调整Adjust_up(bnode->arr, bnode->size);
}2.堆的删除（涉及向下调整）：
为了满足后续的部分需求，堆删除的都是首元素，但堆的底层是数组，删除后会挪动数据而影响效率，切挪动后会破坏原本的父子关系（比如第二层没有关系的两个节点，在挪动后就有了父子关系）。所以堆的删除不能走寻常路，相关操作如下。
- 交换首尾数据（数组具有随机访问的特性，执行这样的操作十分迅速）。
- 删除尾部数据(只用让数据个数size减一就可以)。
- 从新的首元素开始向下调整。
//向下调整算法
void Adjust_down(datatype* arr, int size，int father)
{int child;while (2 * father + 1 < size ) //防止father是叶子节点{child = 2 * father + 1;if (arr[child] > arr[child + 1]) //'> '是维持小堆，'<'值维持大堆{if(child+1<size) child += 1;}if(arr[father] > arr[child]) //'> '是维持小堆，'<'值维持大堆{Swap(&arr[father], &arr[child]);}else{break;}father = child;}
}
//尾部删除
void PopBinary(binary* bnode)
{assert(bnode->size > 0);Swap(&bnode->arr[0], &bnode->arr[bnode->size - 1]);--bnode->size;Adjust_down(bnode->arr, bnode->size,0);
}建堆算法(将一组没有堆特性的数据原地修改为大、小堆)：
1.向下调整建堆
思路分析：数据都是现成的，不需要插入，只需要向上调整。因此可以模拟插入的过程，假设数组只有1个、2个、3个……最后是size个，每次都对我们假设中的尾数据执行向上调整，随着我们依次对数组的每个元素都进行了一次向上调整，杂乱无章的数组数据就具有了堆的特性。
//向上调整建堆
void Adjust_up_set_heap(datatype* arr, int size)
{for (int i = 1; i <= size; i++) //假设数组元素只有1个、2个、3个……{Adjust_up(arr, i); //向上调整算法}
}2.向上调整建堆
思路分析：向下调整建堆比较巧妙，从最后一个叶子节点的父亲节点开始，依次向前遍历，每次对遍历到的节点执行向下调整。直到对根结点进行了向下调整，我们就会发现堆建好了。
//向下调整建堆
void Adjust_down_set_heap(datatype* arr, int size)
{for (int i = (size - 1 - 1) / 2; i >= 0; i--) //size-1为最后一个元素，再减一除二为最后一个叶子结点的父节点{Adjust_down(arr, size,i);}
}堆的应用：
1.堆排序(向下调整)
原理分析：有大和小两种堆，也就是说第一个元素只能是最大或者最小的。因此，可以在堆删除的思想上添枝加叶：先将无规律的一组数建为大(小)堆，然后每次将最大（最小）的首元素和尾元素交换，再将size减1(可以防止后续的操作改动这个最大或者最小的元素)，接着对大小不明的新的首元素进行向下调整(可以维持大堆或小堆的特性)。
排升序：用大堆(大堆的首元素总是最大的，因此每次首尾交换时堆中最大的元素都会到尾部，之后是次大的)
排降序：用小堆(逻辑和排升序相反，每次交换到末尾的数据都是堆中最小、次小的数，正着看就是从大到小的降序了)
下面是建小堆来排降序的核心代码
int arr[] = { 4,3,7,1,5,9,2,4,5 };
int size = sizeof(arr) / sizeof(arr[0]);Adjust_down_set_heap(arr, size);//建小堆int i = size;
while(i>0)
{Swap(&arr[0], &arr[i-1]);i--;Adjust_down(arr, i, 0);
}测试结果如下：
2，topk问题(取得一组数据中最大或最小的k个数)
原理分析：以取得最大的k个数为例，创建一个可以容纳k个数据的数组，将待处理数据中的前k个数使用堆的插入来调整为小堆(小堆可以保证更大的元素总在根节点之下)，再依次从第k+1个数开始向后遍历，将遍历到的每个数和小堆的根节点的值比较，大于根结点的值则交换(否则继续遍历)，并向下调整保持小堆的特性。当遍历结束，最大的k个数就都在这k个数的小堆里了。
//生成了1000000个随机数，并用文件指针pflie当作索引
………………//读取前k个元素
int index = 0;
for (int i = 0; i < k; i++)
{if (fscanf(pfile, "%d", &arr[index++]) != 1){break;}
}
//建小堆
Adjust_down_set_heap(arr, k);//将剩下的数和小堆的根节点比较
int val;
while (fscanf(pfile, "%d", &val) == 1)
{if (val > arr[0]) //大于根节点的值就交换{Swap(&val, &arr[0]);}Adjust_down(arr, k, 0); //维持小堆的特性
} 测试结果如下：
堆相关的代码总览：
堆的核心代码实现就结束啦，下面做一个汇总，并添加一些简单却必要的函数，比如判空、获取元素个数啥的。
头文件
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<time.h>typedef int datatype;
typedef struct binary
{datatype* arr;int size;int capacity;
}binary;
//初始化
void InitBinary(binary* bnode);
//销毁
void Destory(binary* bnode);
//获取元素个数
int Size(binary* bnode);
//判空
int Empty(binary* bonde);
//获取堆顶元素
int Top(binary* bnode);
// 交换值
void Swap(datatype* val1, datatype* val2);
//向上调整算法
void Adjust_up(datatype* arr, int size);
//尾插
void PushBinary(binary* bnode,datatype val);
//尾部删除
void PopBinary(binary* bnode);
//向下调整算法
void Adjust_down(datatype* arr, int size,int father);
//向上调整建堆
void Adjust_up_set_heap(datatype* arr, int size);
//向下调整建堆
void Adjust_down_set_heap(datatype* arr, int size);源文件
#include"test.h"
//初始化
void InitBinary(binary* bnode)
{bnode->arr = NULL;bnode->capacity = bnode->size = 0;
}
//销毁
void Destory(binary* bnode)
{if (!Empty(bnode)){free(bnode->arr);bnode->arr = NULL;bnode->capacity = bnode->size = 0;}
}
//判空
int Empty(binary* bonde)
{return bonde->size == 0;
}
//获取元素个数
int Size(binary* bnode)
{return bnode->size;
}
//获取堆顶元素
int Top(binary* bnode)
{if (Empty(bnode)){perror("empty heap!!!");exit(1);}return bnode->arr[0];
}
//交换值
void Swap(datatype* val1,datatype* val2)
{datatype tmp = *val1;*val1 = *val2;*val2 = tmp;
}
//向上调整算法
void Adjust_up(datatype* arr, int size)
{int child = size - 1;int father = (child - 1) / 2;while (child > 0){if (arr[child] < arr[father]){Swap(&arr[child], &arr[father]);}child = father;father = (child - 1) / 2;}
}
//尾部插入
void PushBinary(binary* bnode,datatype val)
{if (bnode->size == bnode->capacity){int newcapacity = bnode->capacity == 0 ? 4 : 2 * bnode->capacity;datatype* newarr = (datatype*)realloc(bnode->arr, newcapacity*sizeof(int));if (newarr == NULL){perror("realloc fail");exit(1);}bnode->capacity = newcapacity;bnode->arr = newarr;}bnode->arr[bnode->size] = val;++bnode->size;//上面定义过的向上调整算法Adjust_up(bnode->arr, bnode->size);
}
//向下调整算法
void Adjust_down(datatype* arr, int size,int father)
{int child;while (2 * father + 1 < size ){child = 2 * father + 1;if (arr[child] > arr[child + 1]) //'> '是维持小堆，'<'是维持大堆{if(child+1<size)child += 1;}if (arr[child] < arr[father]){Swap(&arr[father], &arr[child]);}else{break;}father = child;}
}
//尾部删除
void PopBinary(binary* bnode)
{assert(bnode->size > 0);Swap(&bnode->arr[0], &bnode->arr[bnode->size - 1]);--bnode->size;Adjust_down(bnode->arr, bnode->size,0);
}
//向上调整建堆
void Adjust_up_set_heap(datatype* arr, int size)
{for (int i = 1; i <= size; i++){Adjust_up(arr, i);}
}//向下调整建堆
void Adjust_down_set_heap(datatype* arr, int size)
{for (int i = (size - 1 - 1) / 2; i >= 0; i--){Adjust_down(arr, size,i);}
}
