基础算法应用场景浅析(2)
堆排序
在我们了解堆排序之前我们需要知道一个概念：树
用简单一点的概念来解释就是：不包含回路的连通无向图。~~解释可能有点生硬，还是用图说话...
例1
上图中左边的是一颗树 右边是一个图 因为左边不包含回路 而右边有1->2->5->3->1这样一个回路。
因为树的不包含回路的特点所以树具有以下特性：
- 在树中任意两个结点连通有且只有一条路径。
- 如果有n个节点那么它构成的边数一定会是n-1条边。
- 在一棵树中加一条边那么将会构成一条回路。
说了这么多树的介绍那么又回到我们的原来的主题，这个应用场景是什么。其实树的应用场景非常非常广泛，我们在平时基本上都要接触到。像我们电脑的文件系统，书的目录，比赛的赛事对决安排表等等......可以说树的应用在我们的生活中基本上是无处不在的。
树的种类
- 无序树:树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
- 有序树:树中任意节点的子结点之间有顺序关系，这种树称为有序树;
- 二叉树:每个节点最多含有两个子树的树称为二叉树;
- 满二叉树： 每个二叉树的结点都有两个子节点
- 完全二叉树：如果一个二叉树除了最右边有一个或者缺少几个叶结点之外，其他都是丰满的 那么这就是完全二叉树。
上面介绍了树的有关概念，我想大家可能对树也有一定的了解了下面进入今天的正题：
堆
堆其实就是一种特殊的完全二叉树，就像下面的树一样
例2
根据上图我们有没有发现一个特点堆顶的数是最小的 左边的树比右边的树下。通俗一点的说法就是父结点比子结点小。（注意：圆圈里面的数代表值 外面的数代表编号）这就是一个最小堆（最小生成树）。
- 案例分析
假设现在有1，2，5，12，7，17，25，19，36，99，22，28，46，92这14个数 现在我需要找出里面最小的数。最简单的办法肯定是用一个for循环 比较得出最小的数
for(int i=1;i<=14;i++)
{
if(a[i]<min) min = a[i];
}
现在我的需求改变了 我需要删除这个数列中最小的数在插入一个数并要求在得出这个数列中的最小的数。您会怎样做？
在大家还没有接触堆这个概念之前，我想大多数人的想法是通过快速或者冒泡等排序方法先找出最小的数将最小的数删除，然后在将新增加的数加入的到数列之中在进行一次排序得出最小的数。即使当我们还不知道有堆排序一说时，我们是不是都觉得是不是很绕或者说很浪费资源。这时专门解决这种疑难杂症的堆排序就应运而生了。
那么我们该如何用？
- 首先我们将数列按照最小堆的原则放入对应的完全二叉树中。如下图所示：
例3
很显然最小的数在堆顶，如果我们需要去掉最小的数 既把堆顶的数去掉，添加新的数放入堆顶。注意：这里还没有完，因为现在的数列不符合最小堆的数列，所以我们需要对这个最小堆进行调整。同时这也是堆排序中的最核心的地方。
- 最小堆的调整
假设现在我们新插入的数是23。如下所示：
例4
1.选在与子结点较小的数进行交换，也就是值为2的数交换
2.交换之后发现23还是比子结点大所以还是不符合最小堆的规则继续交换，同理这次就是与值为7的交换依次比较....
流程如下：
24.png
所以得出的最下堆就是：
25.png
这里最难的也就是向下调整如何用代码的方式来实现。所以这里我拷用我采用java代买实现的片段来说明：
// 这里是生成最小堆的向下调整
// 向下排序 这里是将第i的元素向下确定位置
public static void siftdownMin(int i){
int t = 0;// 这里t是用来作用个临时变量
int flag = 0; // flag 用来判断是不是有改变
while(i*2<= n && flag == 0){
// 首先和左边的子孩子判断大小
if(a[i] > a[2*i]){
t = 2*i;
}else{
t = i;
}
// 判断有没有右边的子孩子
if((i*2+1) <= n){
if(a[t] > a[2*i+1]){
t = 2*i+1;
}
}
// 判断他们之间需不需要交换
if(t != i){
swap(t,i);//这是一个交换方法将下标为值为t和i对应的数组元素交换
i = t;
}else{
flag = 1;
}
// 将他们的值交换
}
}
我相信到这里读者应该都可以看出堆排序的优势了。如果还是有点不敢相信我们可以用数据来判断，如果我们用第一种方法在这14个数中第一次我们找出最小的数我们需要进行14次操作 第二次加入一个新数时，再次取出最小的数我们还是需要在对数组扫描一次 所以经过这两次我们总共需要对数组进行28次操作。现在我们采用第二种方法 第一次我们建立最小堆和上面的第一种方法没有区别也是需要对数组进行全部扫描一遍14次操作，当我们在堆顶插入一个新数时，这时我们从得出最小堆仅仅只需要3步 综合起来我们总共只需要17步就可以完成上述操作，请注意：这是在数很少的情况下我们可能还看不出很大的区别，如果数的个数有1亿个数时我们就可以看出区别了，第一种方法需要计算机运行1亿的平方次数，假设原来的计算机每秒运行10亿次 计算机大约需要1500万秒 也就是100多天 。而第二种方法仅仅只是1亿*log(1亿次)大约等于27亿次 也就是差不多2.5秒 这是一个多么可怕的差距。在这里是不是就体现出如何选择合适算法的重要性了。
唠叨了这么久好像忽略了一个最重要的问题如何建立堆....
如何建立堆
其实我们有了那个调整堆的方法已经可以让我们很轻松的建立堆了。
- 首先我们将一个无序的数列放入完全二叉树中，当然这是一个不和条件的完全二叉树 这时我们只需要调整即可。代码示例如下（java）:
// 首先定义一个交换函数
public static void swap(int x,int y){
int t = 0;
t = a[x];
a[x] = a[y];
a[y] = t;
}
// 向下排序 这里是将第i的元素向下确定位置
public static void siftdownMin(int i){
int t = 0;// 这里t是用来作用个临时变量
int flag = 0; // flag 用来判断是不是有改变
while(i*2<= n && flag == 0){
// 首先和左边的子孩子判断大小
if(a[i] > a[2*i]){
t = 2*i;
}else{
t = i;
}
// 判断有没有右边的子孩子
if((i*2+1) <= n){
if(a[t] > a[2*i+1]){
t = 2*i+1;
}
}
// 判断他们之间需不需要交换
if(t != i){
swap(t,i);
i = t;
}else{
flag = 1;
}
// 将他们的值交换
}
}
// 创建堆
public static void creatHeap(){
for(int i=n/2;i>=1;i--){
siftdownMin(i);
}
}
我相信说到这里堆排序应该怎么写，大家应该都可以很轻松的写出来了。就是每次将堆顶的数取出然后在重新调整堆即可。这里我就不一一说明了。如果有需要的可以留言。下一期给您展出。
