概述
本章继续深入讲解堆，堆是一种特殊的二叉树，具备二叉树特性的同时还具备了一些其他的特性。一般堆使用顺序结构的数组来实现。
一、堆的基本概念
1. 堆
如果有一个关键码的集合 K{k0, k1, k2... ki}，用二叉树顺序存储的方式，以一维数组的形式存储，满足 k(2i+1)（k(2i+2)）<= ki，即孩子小等于父亲，这就是大堆；反之，即小堆。（i=0,1,2……）。将根节点最大的点叫做最大堆或大根堆，根节点最小的堆就是最小堆或者小根堆。
堆具有以下性质：
- 堆中的某个节点总是不大于或者不小于其父节点。
- 堆总是一颗完全二叉树。
完全二叉树的性质： 对于一个具有 n 个节点的二叉树来说，从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号 i：
- 对于序号 i>0（左孩子或者右孩子），他的父亲节点是 (i-1)/2；当 i=0 时，没有父亲节点。
- 若 2i+1<n，则左孩子序号：2i+1。当 2*i+1>n 时，左孩子不存在。
- 若 2i+2<n，则右孩子序号：2i+2。当 2*i+2>n 时，右孩子不存在。
2. 堆的实现
堆的实质上是一个一维数组，先构建起一个结构体，记录数组的现存大小和整体大小，基础实现接口如下：
void HPInit(HP* p1){
assert(p1);
p1->a = NULL;
p1->size = p1->capacity = 0;
}
void HPDestroy(HP* p1){
assert(p1);
free(p1->a);
p1->a = NULL;
p1->size = p1->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2){
HPDataType tmp;
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
bool HPempty(HP* p1){
assert(p1);
return p1->size == 0;
}
HPDataType HPTop(HPDataType* a){
assert(a);
return a[0];
}
