C数据结构-堆的实现思路和堆排序的实现

前言：
在了解完二叉树的相关概念之后，我们就可以来学习下一个数据结构的实现了—堆！
源代码放在最后，需要的自取

堆和前面的数据结构比起来，对小白来说还是有一些难度的，因为堆的逻辑结构看起来更适合用链表来实现，但是实际却是使用数组更加的好一点（后面分析），这就导致后面的内容可能不是那么的好理解，当然比较复杂的部分，我都会结合画图和动图的方式，给大家展示出来！不必担心。

堆的定义

堆（Heap）的定义：
现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。
堆总是满足下列性质：

1. 堆中某个结点的值总是不大于或不小于其父结点的值；
   堆的某个结点总是比其父亲结点小的，称为大堆，如下图：
   

反之被称为小堆，如下图：

2. 堆总是一棵完全二叉树。
   这也是堆能使用数组实现的一大重要的特征。

了解过二叉树的同志们，肯定知道，对于普通的二叉树肯定更加的适合用链式的存储方式来链接，但是，对于完全二叉树，使用数组会更加的高效一些（当然也可以是同链式存储）。

为什么使用数组？

因为数组在内存中是连续开辟空间的，所以可以更好的随意读取想要的元素，而且能更好的找出最大的前几个数，链式结构的话，就必须每次都遍历一边链表。假如要在某个位置插入或删除的元素的话，链式结构还需要用一个指针来记录遍历指针的前一个位置，以达到删除和添加元素的目的。

比起链式的存储结构，使用数组也会让我们在后面实现堆的各个函数接口上，简单很多（比如返回堆低的元素）。

下面我们就来谈谈怎么把一个完全二叉树（堆）的数据放入数组中。

从上到下，从左到右
将堆顶的第一个元素作为数组的第一个元素存放在数组中去，然后是第二层从左到右依次存放到数组，然后到第三层…依次类推。
图解如下：

同样要从数组中将数据取出来，画成逻辑图的话，也是这种方式，所以在学习堆的时候，看不懂的地方要多画图出来。同时大家看到一个数组的时候，也要能看到上图右边的逻辑结构图。

堆接口函数的实现

这里先将所有的接口函数给大家展示出来，让大家大概的明白后面我们要实现那些功能。另外需要解释的一点就是堆的初始化代码。

因为堆使用数组实现，所以使用一个指针来指向存放数据的数组，因为要考虑到扩容的问题，所以并没用选择直接使用一个数组来存放数据。同样的使用一个szie变量来表示当前堆中的数据个数，使用capacity表示数组容量的大小。

一下就是Heap.h的所有内容

堆的初始化

接下来就是各个函数接口的实现问题了，我们先来看第一个，堆的初始化问题。
堆的初始化其实很简单，根我们前面所实现的动态顺序表很相似。

我们这里给定的数组的初始大小为4个int。

堆的销毁

因为是使用的数组，不需要像链表那样一个一个释放。销毁堆的时候直接free掉就好了。

堆的打印

因为size是表示数组中的数据个数，同时也是最后一个数据位置的下一个位置，比如数组此时有两个数据，那么size==2，就如下图：

所以我们通过控制size就可以打印出，堆中的数据。

堆的插入！！

堆的插入和删除是实现堆的重点内容，因为我们要保证的是，在插入一个数据和删除一个数据，之后剩下的数据，仍然是一个大堆或小堆（我们依实现大堆来写代码）。

这个部分的讲解要结合堆的逻辑图来看，假如我们要在下图中的堆中插入一个新的数据 55 。

新插入的数据肯定是插入到数组的最后面（假设数组已经扩容完成了），那么55的位置应该如下图：

此时再去看这个堆，已经不符合堆的定义了，堆要么是大堆（所有的结点都比父亲结点要小）要么是小堆（所有的结点都比父亲结点要大）。而55的到来，明显的破坏了原来大堆的结构，怎么办呢？

首先，我们将55和它的父亲结点进行比较，如果比起父亲结点要大的话，就交换彼此然后再和新的父亲结点进行比较…知道登顶或者没有其父亲结点大，就停止。
图解如下：

如此以来就顺利的完成了堆的插入。

那么大思路确定了之后，我们就来考虑怎么去找到某个结点的父亲结点。观察上图中的红色数字我们可以发现一个规律（父亲结点我们用paent表示，当前结点，即孩子结点用child表示）

堆中数据的孩子和父亲结点的关系满足以下表达式：
leftchild = 2parent+1;
rightchild = 2parent+2;
parent = (child-1) / 2;

不必关心该公式怎么来的。

有了这个重要的条件之后我们就能来着手写代码了。

同样的在插入数据之前要先检查扩容的问题

我们重点来看，Adjuaiup函数的实现。该函数的前半部分看不懂的建议重新去复习一下该专栏的顺序表的实现。

刚才我们已经将整体大的思路讲了，但是对于循环比较父亲结点的结束条件还没说，下面我们还是以55为例来看一下完成的插入过程。

我们可以看到，当child<0的时候，代表已经将需要比较的父亲结点全部比较完了，循环也就结束了。
下面给出代码，对于交换的部分我们还是封装成一个函数，因为后面还需要用到交换的功能。


在实现交换的函数的时候，注意传的是地址，因为形参的改变并不影响实参！！！

到此堆的插入就结束了，下面是测试代码和结果：

大家可以自己将测试的用例的逻辑结构画出来看一下是不是大堆。

堆的删除！！

如果插入完全理解了之后，对于删除其实也大差不差。

我们要删除的是堆顶的数据，删除完成之后保证剩下的数据还是大堆的结构。以上面的测试用例数据为例，我们来看一下如何完成删除。

删除的思路我们就不拐弯抹角了，直接给出

1. 堆顶和堆低的元素交换，size–，删除堆低（原堆顶）的数据。
2. 通过根结点找到两个孩子结点，
3. 选出两个孩子结点较大的那个和根节点进行比较
4. 交换
5. 更新父亲结点更新孩子结点
6. …依次类推

图解如下：

关于怎么通过孩子找父亲和通过父亲找孩子，在上面我们已经说了。
接下来就是调整函数的实现了。

相信这个过程大家不难理解，接下来就是代码，大家可以试着跟着代码走一遍以加深理解。

删除数据时候，需要注意的一点就是，如果堆中没有数据，就不能删除，所以要加上一个assert(php->size > 0)断言一下，确保删除是有效的。

以上就是堆的删除。

堆的判空

解决了堆的两大难题之后，后面的都是虾兵蟹将了，一看就懂，直接上代码。

返回堆顶的元素

堆的大小

堆排序的实现！！

学完堆的实现之后，我们就来看一中与有关的排序–堆排序。

通过前面的学习我们了解到，给定如何一个数组，我们都可以将它看作是堆这种数据结构。由此衍生出了，堆排序。

堆排要做的事情就是将一组数组变成大堆或者小堆。

实现堆排序的两种方式

前面我们已经实现了两种调整堆的方式，我们先来使用第一种Adjustup（向上调整）来看一下怎么将凌乱的数据调整成堆的。
向上调整的方式是通过孩子结点去找父亲结点。
所以在每次调用Adjustup函数的时候，都需要将i作为孩子结点传入。

这个过程也就是将数组中的数据一个个插入的方式建堆。其时间复杂度我们等会再分析。

另外一种方式就是用Adjustdown来实现堆。
Adjustdown建堆的方式就不一样了，我们用动图来展示Adjustdown的建堆过程。

1. 先通过最后一个元素找到其父亲结点
2. 比较大小后交换，然后找倒数第二个数据
3. 找到其父亲结点，再比较进行交换。
4. 找到倒数第三个结点…依次类推。

图解：

下面是代码实现。

sz是数组大小，sz-1是找到最后一个元素，再-1， / 2 是找到父亲结点。
通过控制i–，将数组中的所有数据与其父亲结点进行比较依次来达到建堆的目的。

下面是这两种方式的完整代码。

下面就是时间和空间复杂度的分析。

时间复杂度的分析

判断一个算法的好坏我们总是要通过时间复杂度来分析的。

我们先来看第一种的方式的时间复杂度。
第一种方式有两个过程，一是通过控制 i-- 是使每个数据都向上调整，第二就是数据的调整过程了。
第一个过程不难理解，就是O(n)，那么我们依最坏的请况来看第二，向上调整过程的时间复杂度。

我们之前谈过完全二叉树的高度和结点问题，得出一个表达式

n表示结点的个数，h表示二叉树的高度。

谈论时间复杂度都是以最坏的情况讨论，所以我们就暂时将完全二叉树看作满二叉树。
那么得出：

所以一个数据最坏的调整时间为logn，那么最坏的情况就是每个数据都需要向上调到堆低才能结束，所以第一种堆排的时间复杂度就是O(n*logn)。

第二种方式就简单多了，因为我们是遍历每一个数据，将其与父亲结点进行比较，如果大于父亲结点就交换，否则就i–，找到下一个数据再与其父亲结点进行交换。

因此第二种方式的时间复杂度为O(n)。

Last

堆的实现代码：
堆的实现
堆和顺序表以及链表比起来。是比较抽象的，前面的数据结构的逻辑图和实际的物理存储方式差不多，看着图就能明白大概的实现过程，但是由于堆的逻辑图和实际选择的存储方式差别太大，所以显得比较的抽象。不过真正理解了过后其实也就习惯了，学习就是逐渐的掌握技能的过程，希望你最后的结果，对得起一路的坎坷。