堆可以理解为一种完全二叉树，因此它可以存储在数组里。他的逻辑结构是一颗完全二叉树，物理结构是一个一维数组。
堆分类堆被分为大堆和小堆
大堆每一个子树都满足双亲大于两个孩子
每个子树都满足双亲小于孩子
注意，堆是无序的，也就是左右可以互换
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a; //指针，指向一个数组，数组里面是HPDataType
size_t size; //当前长度
size_t capacity; //最大长
}HP;
堆的基本操作
创建堆
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
没啥好说的，基本操作[滑稽]
销毁堆void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
入堆
入堆有两步基本操作，先入堆，再向上调整。
以这个大堆为例，我们想插入一个60元素，第一步先把他放在堆中，也就是放在完全二叉树对应的数组的最后一个位置。随后进行向上调整。
先看60和他的双亲哪个大，如果双亲小于60则把60和双亲交换。
** 前面讲过 parent = （child-1）/2 ** 可以拿到双亲下标
第一次向上调整：
再拿60和他的双亲比较，发现60还大于双亲，再调整一次
再比较双亲，发现还是大于，再调整一次。
这时候发现已经到堆顶了，不能再调整，整个堆已经重新被我们调整成为大堆的形式。
据此我们总结出向上调整算法的具体步骤。
- 比较自己和双亲大小
- 根据大堆/小堆判断条件决定是否交换
- 当不满足交换条件或者到堆顶的时候结束向上调整算法。
代码实现：
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity) {
//堆满了
int newCpacity = hp->capacity == 0 ? 4 : 2 * (hp->capacity);
HPDataType* n = (HPDataType*)realloc(hp->a, newCpacity*sizeof(HPtataType);
if (n == NULL) {
exit(-1);
}
hp->a = n; //完成扩容
hp->capacity = newCpacity;
}
(hp->a)[hp->size] = x;//先入堆
int child = hp->size;
hp->size++;
while (child != 0) {
int parent = (child - 1) / 2;
if (hp->a[parent] < hp->a[child]) {
//swap(parnt,child)
int t = hp->a[parent];
hp->a[parent] = hp->a[child];
hp->a[child] = t;
child = parent;//下标往上走
}
else {
//不发生交换直接结束
return;
}
}
}
删除堆顶数据
删除堆顶数据就是删除最小或最大数据，以大堆为例，删除大堆的堆顶，就是删除这个大堆的最大值。
在处理这个问题，我们往往采用堆顶堆底交换+向下调整算法
堆顶堆底交换很好理解，就是把数组第一个元素和最后一个元素交换，然后把最后一个元素拿出来即可。
将堆顶的50与堆底的15交换位置。然后把50Pop出去，得到如图所示的完全二叉树，下面要开始向下调整。
第一次向下调整，根据leftChild = parent2 +1 ； rightChild = parent2+2得到两个child，选出最大的那个，与parent交换，随后把parent赋给那个比较大的child上。（这时大堆调法，小堆只需要找到那个更小的即可）
第二次向下调整，25比20大，25与15交换
这时发现parent没有child了，结束向下调整。
因此我们总结向下调整的步骤
- 比较两个child哪个大（或小）
- 将child与更大的交换
- 看看child是否没有孩子，如果没有孩子就结束调整
代码实现（通俗易懂版）：
void HeapPop(Heap* hp)
{
HPDataType root = hp->a[0]; //拿到根
hp->size--;
hp->a[0] = hp->a[hp->size];//把最后一个放到根的位置
int parent = 0; //
while (parent < (int)hp->size) {
int leftChild = parent * 2 + 1;
int rightChild = parent * 2 + 2; //方便理解实际上不用这莫写
leftChild = leftChild < hp->size ? leftChild : -1;//判断是否出界
rightChild = rightChild < hp->size ? rightChild : -1;
if (leftChild == -1 && rightChild == -1) {
//没有孩子直接调完了
break;
}
else if (rightChild == -1) {
//右孩子为空，也是调完了
//只需要最后一次交换
swap(&(hp->a[parent]), &(hp->a[leftChild]));
break;
}
else {
if (hp->a[leftChild] >= hp->a[rightChild]) {
//左孩子大，左孩子调上去
swap(&(hp->a[parent]), &(hp->a[leftChild]));
parent = leftChild;
}
else {
//右孩子大，右孩子调上去
swap(&(hp->a[parent]), &(hp->a[rightChild]));
parent = rightChild;
}
}
}
return;
}
代码实现（高端版）：
void HeapPop(Heap* hp)
{
HPDataType root = hp->a[0]; //拿到根
hp->size--;
hp->a[0] = hp->a[hp->size];//把最后一个放到根的位置
int parent = 0; //
int child = parent * 2 + 1; //拿到左孩子
while (child < hp->size) {
if (child + 1 < hp->size && hp->a[child] < hp->a[child + 1]) {
//右孩子存在且右孩子比左孩子大
child++; //拿出哪个比较大的孩子
}
if (hp->a[child] > hp->a[parent]) {
//孩子比父母大
swap(&(hp->a[parent]), &(hp->a[child]));
parent = child;
child = parent * 2 + 1;
}else {
//根据堆的特新，一旦不换就结束了
break;
}
}
}
取堆顶
取堆顶本质上是拿到最大或最小元素
HPDataType HeapTop(Heap* hp)
{
assert(hp);
if (hp->size <= 0) {
printf("empty Heapn");
assert(hp->size<=0);
}
//取堆顶，取堆顶本质上是拿到最小或最大的数据
return hp->a[0];
}
和HeapPop接口构成了堆排序！
堆的元素个数int HeapSize(Heap* hp)
{
assert(hp);//hp指针不为空
return hp->size;
}
判断堆是否为空
int HeapEmpty(Heap* hp)
{
assert(hp);
if (HeapSize(hp) != 0) {
return 1;
}
else {
return -1;
}
}
堆排序
堆排序是堆的应用重点。
堆排序本质上很简单，他分为建堆，循环出堆两个操作。核心思想就是利用了大堆的堆顶是一串数字的最大值，小堆堆顶是一串数字的最小值。
因此原则上，把数字降序排列用到大堆，因为拿到的元素是从大到小的堆顶，但是不绝对，咋都可以实现。
代码实现：
void HeapSort(int* nums, int numSize)
{
HP hp;
HeapInit(&hp);//初始化堆
//建堆
for (int i = 0; i < numSize; i++) {
HeapPush(&hp, nums[i]); //依次把数组中的数插到堆里面
}
//出堆
int p = 0;//从0开始放，可以自己改变
while (HeapSize(&hp) != 0) {
//堆不为空
nums[p] = HeapTop(&hp);
HeapPop(&hp);
p++;
}
}
一些小问题
无论向上调整还是向下调整算法，他们本质上都是调整完全二叉树高度次，根据前面讲过的 h = log2(n-1) ，所以向上下调整算法的时间复杂度是log(n)
而堆排序在建立堆的时候需要对n个元素都进行向上调整算法，所以时间复杂度是n*logn。
