概念
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
1、堆中某个结点的值总是不大于或不小于其父结点的值。
2、堆总是一棵完全二叉树。建议不了解完全二叉树概念的先去学一下完全二叉树。
根结点的值最大的堆叫做大根堆或者最大堆，根结点的值最小的堆叫做小根堆或者最小堆。
堆是一种非线性结构，是完全二叉树的一种特殊形式，他符合完全二叉树的所有性质。一般使用数组来表示，虽然使用顺序存储结构很难表示出树的父子结点之间的关系，但是完全二叉树是个例外，将完全二叉树的结点按从上到下、从左到右的顺序进行编号，对应数组下标，是可以用数组进行表示的。父子结点的下标对应关系如下：
若序号从0开始，设一个结点的的下标为i，其父结点的下标为(i - 1) / 2，左孩子结点下标为i * 2 + 1，右孩子结点下标为 i * 2 + 2。
例如上图的小根堆，他的数组存储结构如下：
1的左孩子结点为i * 2 + 1 = 1，右孩子结点为i * 2 + 2 = 2。6的父结点为(i - 1) / 2，左孩子结点为i * 2 + 1 = 3，右孩子结点为i * 2 + 2 = 4。
例如上图的大根堆，他的数组存储结构如下：
10的父结点为(i - 1) / 2，左孩子结点为i * 2 + 1 = 3，右孩子结点为i * 2 + 2 = 4。
堆的操作包括创建、插入、删除、返回堆顶元素、摧毁等，下述操作均以大根堆为例。小根堆的操作和大根堆类似。
堆的创建
要创建一个堆，首先要明确其数据结构类型，我们使用的是顺序存储结构也就是数组作为存储结构，堆的结构体定义和初始化如下：
typedef int ElemType;
typedef struct heap
{
ElemType *datas;
int size;
int capacity;
}*max_heap;
max_heap heap_init(int max_size)
{
//申请堆结构体的内存
max_heap heap = (max_heap)malloc(sizeof(struct heap));
//申请数组的内存
heap->datas = (ElemType *)malloc(max_size * sizeof(ElemType));
//初始化当前元素个数为0
heap->size = 0;
//初始化堆的最大存储空间
heap->capacity = max_size;
//返回堆结构体指针
return heap;
}堆的插入
堆插入的基本思想是每次插入都是将先将新数据放在数组最后，由于从这个新数据的父结点到根结点必然为一个有序的序列，现在的任务是将这个新数据插入到这个有序序列中，使其符合堆的特性，这就类似于直接插入排序中将一个数据并入到有序区间中，这也就是堆的向上调整方法。
我们以下图中的大根堆为例，插入一个元素new_data。
将new_data插入到数组的最后位置。
根据new_data的数值不同会有多种情况，以下分情况讨论：
情况一：若new_data为3，我们可以看到从15-6-3，依然是一个有序序列，且符合大根堆的父子结点关系。插入完成。
情况二：若new_data为9，我们可以看到15-6-9，就不是一个有序序列，也不符合大根堆的关系，这时候我们就需要将6和new_data进行互换，交换之后的15-9-6，就满足大根堆的特性了。
情况三：若new_data为23，可以看到15-6-23，也不符合大根堆特性，将6和new_data互换，15-23-6仍然不符合特性，那么就再将其互换，23-15-6就符合大根堆的特性。
//在堆中插入一个元素
bool heap_insert(max_heap heap,ElemType data)
{
//如果堆满则返回false
if(heap->size == heap->capacity)
return false;
int i = heap->size;//当前插入位置，数组的最后
//判断其父结点的值是否大于data，若不大于data，则将父结点下移，再判断其父结点的父结点，类似于直接插入排序
while(heap->datas[(i - 1) / 2] < data && i > 0)
{
//将当前结点的父结点下移
heap->datas[i] = heap->datas[(i - 1) / 2];
//更新当前结点
i = (i - 1) / 2;
}
//最终i就是正确的插入位置。
heap->datas[i] = data;
//堆中元素个数+1
heap->size++;
return true;
}堆的删除
堆中每次都只能删除堆顶元素。删除了堆顶元素之后就要对堆进行重建，重新补充堆顶元素，此时就将数组最后的元素移动到根结点，然后再从根结点开始进行一次从上到下的调整。先判断孩子结点是否比根结点大，若孩子结点都比根结点小，则不需要调整，若孩子结点比根结点大，则要在孩子结点中挑出一个大的进行互换，因为大根堆的堆顶元素是最大的，之后依次向下调整，直到结点没有孩子结点为止。
以下图中的大根堆为例，删除其堆顶元素。
删除之后用数组末尾的元素补充。
之后进行大根堆的向下调整过程，根结点的两个孩子结点都比它大，应该挑两个中的最大，所以将10和4互换位置。
继续比较4的孩子结点，两个孩子结点都比4大，所以再挑两个中的最大，将4和8互换位置。
最后发现4已经没有孩子结点，向下调整结束。最终符合大根堆特性。
bool heap_delete(max_heap heap)
{
//判断堆是否为空
if(heap->size == 0)
return false;
//堆中元素个数-1
heap->size--;
//从根结点开始向下调整
int i = 0;
while(1)
{
int left = i * 2 + 1;//记录左孩子结点
int right = i * 2 + 2;//记录右孩子结点
int max_child = left;//默认最大为左孩子
//找到最大孩子,当右孩子存在且比左孩子大时修改为右孩子，否则默认为左孩子
if(right < heap->size && heap->datas[right] > heap->datas[left])
max_child = right;
//若最大孩子不存在（主要是为了防止左孩子）或者该结点比最大孩子还大，则跳出循环
if(max_child >= heap->size || heap->datas[heap->size] > heap->datas[max_child])
break;
//将最大孩子结点上移
heap->datas[i] = heap->datas[max_child];
//当前结点向下移动
i = max_child;
}
//插入到正确位置
heap->datas[i] = heap->datas[heap->size];
return true;
}堆的构建
堆的构建是将已经存在的N个元素按最大堆/最小堆的要求存放在一个一维数组中。后续的堆排序会用到这种方法。
方法一：通过插入操作，将N个元素一个接一个相继插入到一个初始为空的堆中，时间复杂度最大为O(NlogN)。
int main(int argc, char const *argv[])
{
max_heap heap;
heap = heap_init(20);
int array[10] = {5,6,15,84,65,352,45,32,145,56};
for (int i = 0; i < 10; i++)
{
heap_insert(heap,array[i]);
}
//将数组元素从下标0开始全部打印出来
heap_printf(heap);
heap_destory(heap);
return 0;
}程序将插入之后的数组按下标顺序全部打印出来，运行结果如下：
乍一眼看着打印的内容好像并不符合大根堆的特性，那么我们根据打印结果将其转换为完全二叉树之后如下图，可以看出是符合大根堆的特性的。
方法二：在线性时间复杂度下建立最大堆/最小堆
1、先将N个元素按输入顺序存入，使其先满足完全二叉树的结构特性。
2、再调整各结点位置，使其满足最大堆/最小堆的有序特性。
步骤一显而易见非常简单，就是一个数组的赋值过程，难重点在于步骤二调整结点位置，如果我们从根结点开始调整，使用向下调整的方法，但是这个二叉树本身就是乱序的，他不符合堆的特性，因此无法向下调整，那么我们只能从下开始向上调整。
从下开始调整并不意味着从数组的最后一个元素开始，叶子结点根本就没有子树，他本身无论如何都是一个堆，也就没有调整的必要，所以要从有孩子结点的结点开始调整，使该子树符合堆的特性，直至根结点，最终使整个二叉树符合堆的特性。
下面以一个大小为10的数组为例，int array[10] = {5,6,15,84,65,352,45,32,145,56};先将其填入到一个完全二叉树中。
之后从数组的末尾开始，过滤掉叶子结点，第一个需要调整的就是65这个结点，判断65和56,65 > 56，所以不需要移动，56是叶子结点，所以进行下一个。继续调整84这个结点，他的最大孩子结点为145,145 > 84，则需要调整84和145的位置，其子结点也是叶子结点，所以进行下一个。
15的最大孩子结点为352，352 > 15，需要交换，他的子结点是叶子结点，所以进行下一个。
6的最大孩子结点是145,145 > 6，需要交换，他的孩子结点不是叶子结点，所以需要继续判断。
交换之后的6的最大孩子结点是84，84 > 6，需要交换，其孩子结点为叶子结点，所以进行下一个。
最后到了调整根结点，其最大孩子结点为352，352 > 5，需要交换，其孩子结点不是叶子结点，需要继续判断。
交换之后的5的最大孩子结点为45，需要交换，其孩子结点为叶子结点，所以判断完成。
最终整个二叉树完全符合了堆的特性。
//两种的区别就在于移动，注释掉的是采用临时变量，将两个结点进行交换
//未注释的掉的是使用类似直接插入排序的方法，和堆的删除相同
void heap_creat(max_heap heap,ElemType *data,int size)
{
for (int i = 0; i < size; i++)
{
heap->datas[i] = data[i];
}
heap->size = size;
for(int i = size - 1;i >= 0;i--)
{
int j = i;
int tmp = heap->datas[i];
while (1)
{
int left = j * 2 + 1;//左孩子结点
int right = j * 2 + 2;//右孩子结点
int max_child = left;//默认大的为左孩子结点
//若右孩子存在且右孩子比左孩子大则修改max_child为right
if(right < size && heap->datas[right] > heap->datas[left])
max_child = right;
//若最大孩子不存在，说明已经到了叶子结点
//或者该结点已经比最大孩子还大，符合堆的特性，则跳出循环
if(max_child >= size || tmp > heap->datas[max_child])
break;
//将最大孩子结点上移
heap->datas[j] = heap->datas[max_child];
j = max_child;
}
heap->datas[j] = tmp;
}
}