1.小根堆
若根节点存在左子女则根节点的值小于左子女的值；若根节点存在右子女则根节点的值小于右子女的值。
2.大根堆
若根节点存在左子女则根节点的值大于左子女的值；若根节点存在右子女则根节点的值大于右子女的值。
3.结论
（1）堆是一棵完全二叉树（如果公有h层，那么1~h-1层均满，在h层连续缺失若干个右叶子）。
（2）小根堆的根节点的值是最小值，大根堆的根节点的值是最大值。
（3）堆适合于采用顺序存储。
4.堆的插入算法
将一个数据元素插入到堆中，使之依然成为一个堆。
算法描述：先将结点插入到堆的尾部，再将该结点逐层向上调整，直到依然构成一个堆，调整方法是看每个子树是否符合大（小）根堆的特点，不符合的话则调整叶子和根的位置。
5.堆的删除算法
堆在删除元素时，只可以删除根节点。
算法描述：将根节点删除后用堆尾结点进行填补，调整二叉树，使之依然成为一个堆。
6.堆排序（大根堆，小根堆类似）
其基本思想为(大根堆)：
    1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区，构建的过程是每个非叶子结点都经过一次调整，调整顺序为从底层至顶层(调整过程中含有递归)，这样调整下来这个二叉树整体上就是一个大根堆(或小根堆)了;
    2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
    3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlog2(n)。堆排序为不稳定排序，不适合记录较少的排序。
关于log2(n)的理解：根据堆排序的过程，每次将大根堆根节点的值跟最后一个叶子的值进行交换，那如果最后的叶子结点正好是最小的数，那么这个叶子结点就会一层层的被放到子树最终放到叶子结点的位子（不是前面的叶子结点的位置了），这样的话这个叶子结点经过的层数就刚好为log2(n)。然而其他没有交换的二叉树的分支，因为以前都是大根堆，所以大根堆的性质还是没有变化，这一点对理解程序至关重要。

构建大根堆，同时进行输出排序

#include <string>
#include <map>
#include <iostream>
#include <sstream>
using namespace std;

void PercDown(int A[],int i,int N)   //<i:每个非叶子节点，N数组长度
{  
	int child = 0;
	int Tmp; //<用于保存当前根节点
	for (Tmp = A[i]; (i*2+1)<N; i = child) //<一个循环是因为更新完当前节点后还要看之后的节点是否满足要求
	{
		child = i*2+1;
		if (child != N-1 && A[child+1]>A[child])
		{
			child++; //<选择出子节点中最大的
		}
		if (Tmp < A[child])
		{
			A[i] = A[child];  //<将当前节点由比较大的子节点进行替换
		}
		else
			break;
	}
	A[i] = Tmp; //<i是对应的最后的孩子节点的位置
}  
void main()
{
	int A[9] = {3,8,2,7,9,26,28,54,20};
	int N = 9;
	int i;
	for (i = N/2;i >=0; i--) //<每个非叶子节点,只需要验证非叶子节点
	{
		PercDown(A,i,N); //<i 表示当前需要验证的根节点，N表示数组长度
	}
	for (i = N-1;i > 0; i--) //<这里的i表示数组的长度，因为每一次输出一个数据到vector最后面，树就减少1
	{
		swap(A[0],A[i]);
		PercDown(A,0,i); //<因为每次从堆顶端进行输出，所以每一次验证需要从0开始
	}
	i = 0;
}

#include <string>
#include <map>
#include <iostream>
#include <sstream>
using namespace std;

void PercDown(int A[],int i,int N)   //<i:每个非叶子节点，N数组长度
{  
	int child = 0;
	int tmp= A[i];
	for (; (i*2+1) < N; i = child)
	{
		child = 2*i+1;
		if ((child < (N-1)) && (A[child] > A[child+1])) //<N-1是因为还有有节点
		{
			child++;
		}
		if (tmp > A[child])
		{
			A[i] = A[child];
		}
		else
		{
			break;
		}
	}
	A[i] = tmp;
}  
void main()
{
	int A[9] = {3,8,2,7,9,26,28,54,20};
	int N = 9;
	int i;
	for (i = N/2;i >=0; i--) //<每个非叶子节点,只需要验证非叶子节点
	{
		PercDown(A,i,N); //<i 表示当前需要验证的根节点，N表示数组长度
	}
	for (i = N-1;i > 0; i--) //<这里的i表示数组的长度，因为每一次输出一个数据到vector最后面，树就减少1
	{
		swap(A[0],A[i]); //<注意传入的是i是数组的长度,所以后面的判断是N-1
		PercDown(A,0,i); //<因为每次从堆顶端进行输出，所以每一次验证需要从0开始
	}
	i = 0;
}

堆排序—大根堆，小根堆