前言

本文着重介绍什么是堆和堆的基本算法和基本功能以及堆排序。

一、堆的定义

堆的本质是一个数组，但是这个数组被看作成一棵完全二叉树。

堆分为两种，大根堆和小根堆

1.大根堆

大根堆是每一个节点的值都大于它左右孩子节点的值。
如下图所示，这就是一个大根堆：每个父亲都大于它的孩子。

2.小根堆

小根堆与大根堆相反，每个父亲的节点值都小于它的孩子的值。

如图，这是一个小根堆，其父亲节点的值永远小于左右孩子的值。

当父亲节点的值等于孩子节点的值时，可以叫大根堆，也可以叫小根堆。

通过大根堆和小根堆可以看出，堆未必是有序的。

3.父亲和孩子之间的关系

知道任意父亲节点的下标，可以求出左孩子和右孩子的下标。

parent = (child-1)/2

左孩子或右孩子均可

左孩子：Lchild = parent * 2+1
右孩子：Rchild = parent * 2+2

如下图，当父亲节点为6，其下标为1时，

那么其左孩子下标为1*2+1 = 3

右孩子下标为 1*2+2 = 4

相反，如果知道左孩子下标为3，则其父亲的下标为 (3-1)/2 = 1
如果知道右孩子下标为4，则其父亲的下标为（4-1)/2 = 1

(除法法则向0的方向取整)

二、堆的操作和算法

1.堆的初始化

堆于栈或者顺序表类似，有一个malloc出来的数组和size值，以及capacity值。

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}PHP;void HPInit(PHP* php);void HPInit(PHP* php)
{assert(php);//初始状态设置容量4大小HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * 4);assert(tmp);php->a = tmp;php->size = 0;php->capacity = 4;
}

2.堆的插入

在已有堆的基础上，向堆中插入一个数据，但是必须保证插入后，不会改变堆的结构。
也就是说，插入前是大堆，插入后也必须是大堆。

既要插入数据到合适的位置，又要不该变堆的结构，有一种算法可以解决该问题：

向上调整算法

以该图片的例子为例：在已有堆的基础上插入一个60：

这个按照原来的堆是大堆这个60是所有元素中最大的数，应该插入到堆顶上。

注意：不能使用挪动数据的方法，即把所有元素往后挪一位进行插入，
1.挪动数据时间复杂度O(n)，效率低
2.挪动已经改变了原来堆的结构，挪动之后很有可能不再是堆了。
3.如果插入的数据不是最大的或最小的，无法判断该往哪个地方插入。

向上调整算法流程如下：
假设原本的堆是大堆
1.记录该插入元素的父亲的下标。

2.将要插入的元素和其父亲做比较，如果孩子大于父亲，那么将孩子和父亲进行交换。

3.父亲和孩子迭代往上走，再进行判断，重复第二步的过程。

实现代码如下：

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//不能用这样的循环写法,有潜在的越界风险//while(parent>=0)//因为parent不会小于0，当child为0时，child-1 = -1，-1/2 = 0,parent最小也是0，不会结束while循环//但是这段代码是能正常运行的，因为只要child小于parent了，那就break。while (child > 0){//现在是大堆，如果要小堆，就改一下成小于号if (a[child] > a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

注意：
在循环条件判断时，不能用parent>=0来作为继续条件，
1.parent不会是负数，因为当child为0 时，
parent = (child-1)/2 = 0，这个条件不会终止循环
所以只能用child>0来进行终止。

总插入代码如下：

void HPPush(PHP* php, HPDataType x)
{assert(php);//插入之前先判断容量if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);assert(tmp);php->a = tmp;php->capacity *= 2;}//开始插入php->a[php->size++] = x;//插入完成后，开始向上调整AdjustUp(php->a, php->size - 1);}

向上调整算法时间复杂度

假设这个堆的高度为h，则在最坏情况下，最后一层的每个节点向上调整的次数为(h-1)次，一共有2^(h-1)个节点，那么最后一层调整的总次数为 :2^(h-1)*(h-1)次，假设总调整次数为T(N)次，由于第一个节点不需要调整，则有：

由错位相减法：

推导如上：则向上调整算法的时间复杂度为O(N*logN)

3. 堆的删除

假设一个堆为大根堆，
对于堆的删除来说，删除堆尾元素没有意义，删除堆顶元素才有意义，因为堆顶元素是最大的，只有把最大的元素删除了，才能筛选出次大的，只有把次大的元素删除了，才能筛选出次次大的，这样即可以达到一个排序的效果也不会破坏堆的结构。

注意：堆的删除同样不能使用数组往前覆盖的方法进行删除。
1.往前覆盖时间复杂度O(N)，效率不高
2.往前覆盖会导致堆的父子关系和兄弟关系造成紊乱，破坏了堆的结构。

向下调整算法

所以堆的删除使用向下调整的算法：

步骤如下：
假设是大根堆的条件下：
1.交换堆顶和堆尾的两个数据，这样堆的最大元素就被删除了。
2.为了保证堆的结构不会被改变，需要把现在堆顶的元素向下调整。先记录堆顶下标，即parent，再记录孩子下标，因为可能有左孩子和右孩子，不知道谁大，那么我们先假设左孩子大，然后再将左孩子和右孩子进行比较，谁大就再跟父亲进行比较，如果父亲小于孩子，那么父亲就要向下调整。

实现代码如下：

//1.向下调整算法一开始是用来实现堆的删除的
//删除是专门用来删除堆顶元素的，这样才有意义
// 假如是一个大根堆，那就把堆顶删了，把老大删了，这样才能筛选出老二
//把老大删了的做法：把堆顶元素和最后一个元素交换，然后size--
//然后堆顶元素和左右孩子比较，大的孩子做堆顶，这样就实现了推老二上堆顶。
//然后这个在老二位置的这个元素继续向下调整，就是实现了堆的删除
//删除堆顶元素又保证了原来是大堆，删除之后还是大堆的情况，不会导致兄弟父子关系错乱。//删除堆顶元素不能用向上调整的算法，因为用向上调整//2.后来向下调整算法不仅仅可以用来进行堆的删除元素
//还可以用来实现建堆，下面会提及
void AdjustDown(HPDataType* a, int n, int parent)
{//假设左孩子就是最大的int child = (parent * 2) + 1;while (child < n){//筛选左右孩子谁大
//		if(a[child+1]>a[child]),不能这样判断//(因为有可能存在右孩子不存在的情况，需要判断一下右孩子是否存在)//否则容易出现越界问题
//		if (a[child + 1] > a[child] && child + 1 < n )
// 也不能这样写，这样写跟上面的写法一样了if (child + 1 < n && a[child + 1] > a[child]){child++;}//大孩子和父节点交换if (a[child] > a[parent]){swap(&a[child], &a[parent]);//交换之后往下走，parent = child;child = (parent * 2) + 1;}else{break;}}
}

注意：在比较左右孩子的大小时，不能直接判断，要先判断右孩子是否存在。

注释有些重要的细节，请认真查看。

向下调整算法时间复杂度：

向下调整不同于向上调整，向下调整节点开始调整是从第一个非叶子节点开始调整的：

因为最后一排不需要向下调整
推导如下：

所以向下调整算法的时间复杂度为O(N)

有一个比较好的方法判断向上调整快还是向下调整快：
直接看堆的最后一行，

向上调整算法中：堆的最后一行调整次数为2^(h-1)*(h-1)次，

向下调整算法中：堆的最后一行不需要调整，

倒数第二行才需要调整，且调整次数为2^(h-2)* 1。

对比对比就知道了。

三、堆排序

前面讲的堆的插入和删除操作，都是有前提的，必须在已经有堆的前提下才能使用向上调整算法和向下调整算法。

其实，向上调整算法和向下调整算法可以单独使用建成一个堆。
使用向上调整法建堆如下图：

结果如下：

时间复杂度为O(N*logN)

向下调整建堆如下图：

时间复杂度O(N)

堆排序：
使用向下调整的方法进行堆排序：

	堆排序使用交换之后再向下调整原理：在建了大根堆之后，堆顶的左右子树都是大根堆，不管最后一个元素是否是最小的，与堆顶元素交换后堆顶元素就被放到了堆尾，然后再让堆顶元素向下调整，因为此时堆顶元素是一个较小的元素，会向下调整，调整之后是第二大的元素在堆顶下一次再排序时，排的是堆尾的前一个了，那个最大的元素不用再排了，排的就是第二大的元素，再让堆的最后一个元素与堆顶元素交换，再进行向下调整，调整完后第三大的元素就上来了。

堆排序代码如下：

void HeapSort(int* a, int n)
{assert(a);//1.先建堆，向上调整建堆,建堆的时间复杂度为O(N*logN)//也可以采用向下调整的方法建堆，向下调整的方法建堆的时间复杂度为O(N)//强烈建议采用向下调整的建堆方式//for (int i = 0; i < n; ++i)//{//	AdjustUp(a, i);//}//向下调整建堆，是从第一个非叶子节点开始调整，因为所有的叶子节点都不需要进行向下调整//child = (parent-1)/2//此时parent就是n-1for (int i = (n - 1 - 1) / 2; i >=0; -- i){AdjustDown(a, n, i);}//现在是大根堆//2.堆排序，采用向下调整算法进行排序,让最后一个节点和堆顶节点进行交换，然后堆顶节点向下调整//调整完后继续倒数第二个节点和堆顶节点交换,以此类推for (int i = n-1; i >0; --i){swap(&a[0], &a[i]);//这里传参不能传n，传n-1,因为交换之后最后一个数字就不需要参与进来了，相当于size--//堆排序使用交换之后再向下调整原理：//在建了大根堆之后，堆顶的左右子树都是大根堆，不管最后一个元素是否是最小的，与堆顶元素交换后//堆顶元素就被放到了堆尾，然后再让堆顶元素向下调整，因为此时堆顶元素是一个较小的元素，会向下调整，调整之后是第二大的元素在堆顶// //下一次再排序时，排的是堆尾的前一个了，那个最大的元素不用再排了，排的就是第二大的元素，//再让堆的最后一个元素与堆顶元素交换，再进行向下调整，调整完后第三大的元素就上来了。AdjustDown(a, i, 0);}//总结：排升序的话，建大根堆//排降序建小根堆for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}