二叉树的性质：
在我们实现堆之前我们要知道堆的实现是依靠的是二叉树 所以我们在实现对之前要了解一下二叉树的基本性质：>
- 如果根节点的层数为1，则一个非空二叉树的第 i 层上最多有2^(i-1)个节点
- 若规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^h - 1
- 对于任何一棵二叉树，如果度为0的节点个数是n0，度为2的分支节点个数为n2，则有n0=n2+1
- 如果说根节点的层数为1，那么具有那个节点的满二叉树的深度 h=log2(n+1);
这些就是我们二叉树的一些基本性质
二叉树的存储结构：
二叉树一般有两种存储结构 一个顺序结构 一个链式结构
顺序存储：
顺序存储顾名思义 就是存储的数据是有一定顺序的 所以顺序存储就是用数组来进行存储 但是使用顺序存储一般用来存储完全二叉树 因为不是完全二叉树会有空间的浪费（就是有些地方应该为NULL 那么在数组里面这些地方也应该空着 它们只能属于自己的位置）
像这样大家应该就知道如果说不是完全二叉树使用顺序结构的话 会有空间的浪费 数据越多浪费的空间也可能更多
链式存储：
链式存储意思就是用链表来表示 一个链表的节点就包括 这个节点的数据和左右节点的指针
typedef struct BinaryTreeNode { int data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
堆的概念和性质：
堆 其实就是 一个完全二叉树 其中堆又分为 小堆 和 大堆
小堆 就是 根节点是所有数据中最小的
大堆 就是 根节点是所有数据中最大的
堆的实现：
首先这里我们就用 数组 的方式来存储数据
typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }Heap;
另外有个点大家要注意 我们的堆是不支持什么在 中间 插入删除数据的 这种操作是顺序表中使用的 但我们的堆虽然是使用的数组的结构 但那只是物理上面的 逻辑上面可不是那样的哦
这里我们为什么还有一个size capacity呢 这两个参数是用来判断是否扩容的 我们这里设置的是一个动态增长的数组
堆的初始化：
void HeapInit(Heap* hp) { assert(hp); hp->a = NULL; hp->size = hp->capacity = 0; } void HeapDestory(Heap* hp) { assert(hp); free(hp->a); hp->a = NULL; hp->capacity = hp->size = 0; }
堆的插入：
我们先了解一下堆的插入是如何实现 首先我们的堆的结构是一个动态的数组 我们在他的尾部插入数据 但大家想想仅仅只是把数据放进去就完了嘛 我们上面说过我们堆里面的数据位置是有讲究的 如果说随便改变是有可能会把我们之前建立的结构破坏的
所以如果我们建立的是一个小堆的话 现在放进去一个较小的数据 那么这个数据肯定是要往前面进行调整的 不然我们的堆就不是小堆 :>
看过上图 大家应该知道我们 因给如何调整我们的堆结构了把：
就是 向上调整
这个就是我们的向上调整的整体操作
void HeapPush(Heap* hp, HPDataType x) { if (hp->_size == hp->_capacity) { int newcapcity = hp->_capacity == 0 ? 4 : hp->_capacity * 2; HPDataType* tmp=(HPDataType *)malloc(newcapcity * sizeof( HPDataType)); assert(tmp); hp->_a = tmp; } hp->_a[hp->_size++] = x; AdjustUp(hp->_a, hp->_size - 1);//因为我们我们调整是从最后一个数据开始调 所以要传他的下标 }
因为我们堆的实现物理上还是依靠的顺序表 虽说结构上是树 但我们在插入数据的时候 难免会遇到要扩容的情况 所以我们使用了 size 和 capacity 来实时监控我们的空间
然后就来看我们的向上调整函数：
向上调整函数：
在实现我们的向上调整函数之前 我们首先要了解 树中 父亲和孩子的关系
左孩子=父亲×2+1
右孩子=父亲×2+2
然后大家想想 其实无论奇数还是偶数 -1÷2 的结果都是一样的 我的编译器 ÷ 是默认的向下取整 带入几个数算了就知道他们的结果都是一样的 但你要-2÷2就不太好了
void AdjustUp(HPDataType* a,int child) { assert(a); size_t parent = (child - 1) >> 1; while (child > 0) { if (a[child] < a[parent]) { swap(a+child, a+parent); child = parent; parent= (child - 1) >> 1; } else { break; } } }
看到这个图大家应该明白我们的child 排到0时 就不用再继续往上调整了
所以我们 设置的外部循环是 child>0 至于为什么不用parent判断 因为parent不会小于0
我们的child等于0的时候 (0-1)/2 parent还是等于0的
里面设置一个if 小于就交换 大于就不用再换了 大于一个数那它都大于它上面的了
然后重新给我们的 child parent 赋值
