前言
本文着重介绍什么是堆和堆的基本算法和基本功能以及堆排序。
一、堆的定义
堆的本质是一个数组，但是这个数组被看作成一棵完全二叉树。
堆分为两种，大根堆和小根堆
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)
注意：如果单独调整某个数字，则时间复杂度为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)
注意：如果单独调整某个数字，则时间复杂度为logN
有一个比较好的方法判断向上调整快还是向下调整快：
直接看堆的最后一行，
向上调整算法中：堆的最后一行调整次数为2^(h-1)*(h-1)次，
向下调整算法中：堆的最后一行不需要调整，
倒数第二行才需要调整，且调整次数为2^(h-2)* 1。
对比对比就知道了。
