TIPS
树的话是一种非线性的数据结构，他实际上就是具有一定层次关系的数据集合，并且在树形结构当中，子树之间不能有任何的交集，否则就不是树形结构。然后对于树而言的话，在实际应用当中并不是特别多，在实际应用当中用的特别多的是二叉树。
对于二叉树这个概念而言，千万不能把二叉树等价于有完全二叉树，实际上二叉树的话，它的样子的话也可以千奇百怪，诸如
因为二叉树他的条件就是说整个树的度<=2就可以了，所以上面这种形态的也可以称之为二叉树，然后平时的接触到的比较多的，一般都是满二叉树或完全二叉树
然后就是关于二叉树节点数量的一些性质：首先是对于任何一棵树而言，度数为0的节点的数量一定比度数为一的节点的数量要多一；然后对于完全二叉树而言，度数为一的点，要么是零，要么是一；接下来在树的第k层当中，节点的数量最多是2的k减1次方，有k层节点的树最多拥有的节点数量是2的k次方减1
完全二叉树高度&深度估算（为后面的堆有关复杂度做铺垫）
如果说一个完全二叉树（满二叉树是完全二叉树的一种特殊情况），他有n个节点的话，那么这时候他的层数（不是精确计算，而是大概估量一下）他的层数是logN。
这个概念非常重要，因为涉及到之后的一个堆排序的一个时间复杂度与效率的计算问题
拉响警报：堆正式降临！！！！！！！！！！！！！！！！！！
二叉树的顺序存储（仅局限于堆与完全二叉树）
对于二叉树而言，它有两种存储方式，一种就是顺序结构，一种是链式结构。
首先，逻辑结构与物理结构的区别还是得知道，在逻辑结构上的话，它是一棵树，但是如果在物理结构上的话，他就是一个数组。逻辑结果的话是想象出来的，有可能与物理结构是一样的，比如说顺序表；有可能是与物理结构不一样的，比如链表或者二叉树。物理结构的话，相当于就是说是实实在在在内存当中是如何存储的。
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
其实要存储的话应该比较简单，就是把这个树里面的一层一层的数据依次往数组里面去存。用数组储存二叉数的话，并不适合随便乱七八糟的一个二叉树，是比较适合满二叉树或者说完全二叉树。如果一个二叉树它并不符合完全二叉树的话，这时候用数组去存储的话，当然也是可以，但是有很多位置会空缺出来，这就会形成浪费。因此的话，用数组去存储二叉数的话是带有局限性。数组存储表示二叉数只适合完全二叉树。
然后需要注意的是就是说二叉树当中每一个节点的下标与数组当中的下标都是一一对应的，见一开始的图。
就可以通过孩子的下标去找到他的父节点的下标。主要是他们之间的下标关系有这样一个结论：parent = (child -1)/2， 然后如果说已经知道父结点的下标，我这时候想要去求他的两个左右儿子的下标，这也非常的简单：主要是他们之间的下标有这样一种关系 leftchild=parent*2+1，rightchild=parent*2+2
堆（二叉树->完全二叉树->儿子总是小于（大于）父亲）
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。
堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
小根堆与大根堆
手撕数据结构—堆（底层为顺序表）
堆的结构体创建
typedef int HeapDataType;
typedef struct Heap
{
HeapDataType data;
int size;
int capacity;
}heap;堆的结构体初始化
#define INIT_CAPACITY 5
void HeapInit(heap* php)
{
assert(php);
php->p = (HeapDataType*)malloc(sizeof(HeapDataType) * INIT_CAPACITY);
if (php->p == NULL)
{
perror("malloc fail");
return;
}
php->capacity = INIT_CAPACITY;
php->size = 0;
}堆的数组元素交换函数
void Swap(HeapDataType* p1, HeapDataType* p2)
{
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}堆的向上更新（以大根堆为例）
void AdjustUp(HeapDataType* a, int child)
{
assert(a);
int parent=(child-1)/2;
while (child > 0)
{
int parent = (child - 1) / 2;
if (a[child] > a[parent])
{
Swap(a + child, a + parent);
child = parent;
parent=(child-1)/2;
}
else
{
break;
}
}
}堆的向下更新（以大根堆为例）
void AdjustDown(HeapDataType* a, int parent, int n)
{
assert(a);
int child = (parent * 2 + 1);
while (child<n)
{
if (child+1< n && a[parent * 2 + 1] < a[parent * 2 + 2])
{
child++;
}
if (a[parent] >= a[child])
{
break;
}
else
{
Swap(a + parent, a + child);
parent = child;
child = parent * 2 + 1;
}
}
}堆的往里面插入一个数值
void HeapPush(heap* php, int x)
{
assert(php);
if (php->size == php->capacity)
{
HeapDataType* tmp = (HeapDataType*)realloc(php->p, sizeof(HeapDataType) * php->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->p = tmp;
php->capacity *= 2;
}
php->p[php->size] = x;
php->size++;
AdjustUp(php->p, php->size - 1);
}堆的删除堆顶元素（堆中最值）
删除堆顶元素，如果在数组那边直接删的话，不仅会导致效率低下，因为需要流动数据，而且会导致父子关系全乱了
void HeapPop(heap* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(php->p + 0, php->p + php->size - 1);
php->size--;
AdjustDown(php->p, 0, php->size);
}堆的求堆顶元素（堆中最值）
int HeapTop(heap* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->p[0];
}堆的判断是否为空
bool HeapEmpty(heap* php)
{
assert(php);
return php->size == 0;
}堆的求堆中元素个数
int HeapSize(heap* php)
{
assert(php);
return php->size;
}首先我们需要知道的是：堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
然后堆中的元素的话并不都是有序的，这个是一个常见的认知误区，尤其对于我这种新手来说。根据堆的定义，它的条件其实说多也不多，说少也不少，他只限定了每个父亲与儿子之间值的大小关系，从整体而言，这个堆的话并不一定是有序的。
虽然并不一定是有序的，我们可以把这个堆称之为半有序状态，因为他也并不是完全无序的，首先对于每一对父亲与儿子之间的大小关系是统一确定的，同时堆顶元素的话也有特殊的含义，堆顶元素整个堆当中所有数据的最值，这一点倒也是毋庸置疑的
然后需要有一种意识：就是你实际上操控的无非就是一个顺序表，说白了就是数组，但是逻辑结构与物理结构之间能够建立联系，说你要想象成你在操控着一颗完全二叉树
任何一个数组，其实如果你看待视角改变一下的话，都可以把它看成一颗完全二叉树，当然是不是堆的话就不一定了，还是那句话：堆=二叉树->完全二叉树->儿子总是小于（大于）父亲即可 （总的条件说多也不多，说少也不少）
