二叉搜索树：
又称二叉排序树，二叉查找树
满足以下性质：
1）没有键值相等的节点。
2）若左子树不为空，左子树上节点值均小于根节点的值。
3）若右子树不为空，右子树上节点值均大于根节点的值。
特点：根节点大于左子树，根节点小于右子树
二叉查找树中对于目标节点的查找过程类似与有序数组的二分查找，并且查找次数不会超过树的深度。最好的情况下，二叉查找树的查找效率为O(log n)；当二叉查找树退化为单链表时，比如，只有右子树的情况,如下图所示，此时查找效率为O(n)。
所以二叉查找树越是“矮胖”，也就是每层尽可能地被“塞满”（每个父节点均有两个子节点）时，查找效率越高；为了解决二叉查找树退化为单链表时查找效率低下的问题，引入了平衡二叉树(AVL，人名)
平衡二叉树：
它是二叉搜索树的一种改进，它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等
平衡二叉树特点
1）父节点的左右两棵子树的深度之差的绝对值不超过1。
堆：
堆是为了实现排序而设计的一种数据结构，它不是面向查找操作的
堆是什么？是一种特殊的完全二叉树，就像下面这棵树一样。
我们发现这棵二叉树有一个特点，就是所有父结点都比子结点要小（注意：圆圈里面的数是值，圆圈上面的数是这个结点的编号），符合这样特点的完全二叉树我们称为最小堆。反之，如果所有父结点都比子结点要大，这样的完全二叉树称为最大堆
假如有14个数分别是99、5、36、7、22、17、46、12、2、19、25、28、1和92。请找出这14个数中最小的数，请问怎么办呢？最简单的方法就是将这14个数从头到尾依次扫一遍，用一个循环就可以解决。这种方法的时间复杂度是O(14)也就是O(N)。
for(i=1;i<=14;i++){
if(a[ i]<min) min=a[ i];
}
现在我们需要删除其中最小的数，并增加一个新数23，再次求这14个数中最小的一个数。请问该怎么办呢？只能重新扫描所有的数，才能找到新的最小的数，这个时间复杂度也是O(N)。假如现在有14次这样的操作（删除最小的数后并添加一个新数）。那么整个时间复杂度就是O(142)即O(N2)。那有没有更好的方法呢？堆这个特殊的结构恰好能够很好地解决这个问题。
首先我们先把这个14个数按照最小堆的要求（就是所有父结点都比子结点要小）放入一棵完全二叉树，就像下面这棵树一样。
很显然最小的数就在堆顶，假设存储这个堆的数组叫做h的话，最小数就是h[ 1]。接下来，我们将堆顶的数删除，并将新增加的数23放到堆顶。显然加了新数后已经不符合最小堆的特性，我们需要将新增加的数调整到合适的位置。那如何调整呢？
向下调整！我们需要将这个数与它的两个儿子2和5比较，并选择较小一个与它交换，交换之后如下。
我们发现此时还是不符合最小堆的特性，因此还需要继续向下调整。于是继续将23与它的两个儿子12和7比较，并选择较小一个交换，交换之后如下。
到此，还是不符合最小堆的特性，仍需要继续向下调整直到符合最小堆的特性为止。
我们发现现在已经符合最小堆的特性了。综上所述，当新增加一个数被放置到堆顶时，如果此时不符合最小堆的特性，则将需要将这个数向下调整，直到找到合适的位置为止，使其重新符合最小堆的特性。
int n =14;
int a[] = {1,2,5,12,7,17,25,19,36,99,22,28,46,92};
int*p = a; p[0] =23;
siftdown(0, n, a); //从编号为0开始向下调整；由于数组从0开始，所以我们编号也从0开始
for(int i =0; i<14; i++) {
cout<<a[i]<<"\n"; 输出2--7--5--12--22--17--25--19--36--99--23--28--46--92
}
我们刚才在对23进行调整的时候，竟然只进行了3次比较，就重新恢复了最小堆的特性。现在最小的数依然在堆顶为2。之前那种从头到尾扫描的方法需要14次比较，现在只需要3次就够了。现在每次删除最小的数并新增一个数，并求当前最小数的时间复杂度是O(3)，这恰好是O(log214)即O(log2N)简写为O(logN)(每次比较完数据剩下一半，比较次数为c，c个2相乘等于N)。假如现在有1亿个数（即N=1亿），进行1亿次删除最小数并新增一个数的操作，使用原来扫描的方法计算机需要运行大约1亿的平方次，而现在只需要1亿*log1亿次，即27亿次。假设计算机每秒钟可以运行10亿次，那原来则需要一千万秒大约115天！而现在只要2.7秒。是不是很神奇，再次感受到算法的伟大了吧。
如果只是想新增一个值，而不是删除最小值又该如何操作呢？
例如我们现在要新增一个数3。
先将3与它的父结点25比较，发现比父结点小，为了维护最小堆的特性，需要与父结点的值进行交换。交换之后发现还是要比它此时的父结点5小，因此需要再次与父结点交换。至此又重新满足了最小堆的特性。向上调整完毕后如下。
void siftup(int i,int *h) //传入一个需要向上调整的结点编号i{
int flag=0; //用来标记是否需要继续向上调整
if(i==0) return; //如果是堆顶，就返回，不需要调整了
//不在堆顶 并且 当前结点i的值比父结点小的时候继续向上调整
while(i!=0&& flag==0){
//判断是否比父结点的小
if(h[i] {
// swap(i,(i-1)/2);//交换他和他爸爸的位置
inttemp = h[i];
h[i] = h[(i-1)/2];
h[(i-1)/2] = temp;
}
else
flag=1;//表示已经不需要调整了，当前结点的值比父结点的值要大
i=(i-1)/2; //这句话很重要，更新编号i为它父结点的编号，从而便于下一次继续向上调整
}
}
int n =14;
int a[20] = {1,2,5,12,7,17,25,19,36,99,22,28,46,92};
int*p = a;
p[0] =23;
siftdown(0, n, a); //从编号为0开始向下调整；由于数组从0开始，所以我们编号也从0开始
for(inti=0; i<14; i++) {
cout<<a[i]<<"--";
}
printf("........");
a[14] =3;
siftup(14, a);
for(int i=0; i<15; i++) {
cout<<a[i]<<"--"; //输出2--7--3--12--22--17--5--19--36--99--23--28--46--92--25
}
创建堆：
void HeapAdjust(int H[],int s,int length){
//此函数的作用是（s代表s号结点）调整s号结点及其下面所有子结点位置
int tmp = H[s];
int child =2*s+1;//左孩子结点的位置。
while(child < length) {
if(child+1H[child+1]) {// 如果右孩子大于左孩子，更新child为右孩子
++child ;
}
if(H[s]>H[child]) { // 如果较大的子结点大于父结点
H[s] = H[child];// 那么把较大的子结点往上移动，替换它的父结点
s = child; // 重新设置s ,即待调整的下一个结点的位置
child =2*s+1;
} else{ // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
break;
}
H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
}
}
void BuildingHeap(int H[],int length)//假设第一个结点为0号结点来创建堆
{ //创建最小堆
//最后一个有孩子的节点的位置 i= (length -1) / 2
for(inti = (length -1) /2; i >=0; --i)
HeapAdjust(H,i,length);
//以3,1,5,7,2,4,9,6,10,8为例子
//第一次 先判断最后一个有孩子的节点2（4号结点
//第二次 判断7这个节点（3号结点）
//第三次 判断5这个节点（2号结点）
//以此类推最后得到堆：10--8--9--7--3--4--5--6--1--2
}
验证：
int a[20] = {3,1,5,7,2,4,9,6,10,8};
BuildingHeap(a, 11);
for(int i=0; i<11; i++) {
cout<<a[i]<<"--"; //输出1--2--3--4--3--9--6--7--13--8--10
}
