堆排序在排序算法中算比较复杂一点的,今天看看它的原理是啥,先来看看实现好的demo:

基础知识

要讲堆排序,首先得要知道什么是堆。堆其实就是一个完全二叉树,那什么又是完全二叉树呢?

满足以下两个条件的就是完全二叉树了:

1.从作为第一层的根开始,除了最后一层之外,第N层的元素个数都必须是2的N次方;第一层一个元素,第二层4个,第三层8个,以此类推。

2.而最后一行的元素,都要紧贴在左边,换句话说,每一行的元素都从最左边开始安放,两个元素之间不能有空闲,具备了这两个特点的树,就是一棵完全二叉树。

下图就是一个完全二叉树:

background Layer 1 1 2 3 4 5 6 7 8

刚才说了完全二叉树的概念,在此基础上,还有两个衍生概念:大根堆,小根堆。

所谓大根堆,就是父节点大于它的左右两个孩子节点,树的根节点是最大的;小根堆则相反,是父节点小于左右两个孩子节点,树的根节点是最小的。(注意:大小堆只是规定了父节点和子节点的关系,同一个父节点下的两个子节点大小无要求)

下图就是大根堆和小根堆:

background Layer 1 90 80 70 66 77 69 50 60 55 10 20 33 30 66 45 52 40 大根堆 小根堆

现在还要讲一个数组对应二叉树的规则:

background Layer 1 6 2 9 1 8 7 3 4 [6,2,9,1,8,7,3,4] 数组: 对应的堆 下标为0 下标为1 下标为2 下标为3 下标为4 下标为5 下标为6 下标为7

大家看上图可以发现,一个数组变成堆,就是把数组里面的内容,从上到下,从左到右放在完全二叉树上就好了,为什么要将这个对应关系呢?因为后续所有对树的操作,其实就是对数组的操作。

background Layer 1 6 2 9 1 8 7 3 4 [6,2,9,1,8,7,3,4] 数组: 对应的堆 下标为0 下标为1 下标为2 下标为3 下标为4 下标为5 下标为6 下标为7 交换 对应数组上的交换 [6,2,9,1,8,7,3,4] 交换

我们可以看到,我们交换树上2和8的位置,真实操作就是交换数组中下标为1和4的元素而已。

堆排序主要原理

现在我们看看堆排序的主要流程:

第一步,我们需要把无序堆变成一个大根堆。

第二步,我们把大根堆的根节点和最后一个节点交换,也就是把数组中的第一个元素和最后一个元素进行交换,为什么这样操作?因为经过第一步之后,我们可以确定一点,根节点一定是最大的,这个毋庸置疑吧?我们和最后一个元素交换,其实也就是相当于说,我们已经确定了一个最大的,把它放在最后,我们现在去前面n-1个元素中再找出一个最大的。交换后,大根堆就破坏了,需要把前面n-1个数字重新变成大根堆。

第三步,我们把前面n-1个数字组成的大根堆中的根节点和最后一个节点交换,也就是把数组中的第一个元素和第n-1个元素交换。为什么是第n-1个元素?因为现在的大根堆是由n-1个元素组成的,第n个元素是我们第一次大根堆得到的,我们把数组中第一个元素和第n-1个元素交换后,第n-1个元素就是整个数组中第二大的数字了。

第四,五,六,..N步,剩下的步骤就差不多了,就是不断的缩小前面大根堆的范围,每次完成一个大根堆,就交换根节点和最后一个节点,进而对前面大根堆进行重排。

将无序堆变成大根堆

把无序堆变成大根堆我们主要考虑纠正每个单元父子节点,因为我们只要保证了每个单元父子节点中父节点是最大的,那么最后肯定也是大根堆了。

background Layer 1 6 2 9 1 8 7 3 4 交换 在这个堆中,有孩子节点的是1,9,2,6,从下往上,从右往左,依次找出自己和孩子中最大的,并把最大的放在父节点上。 6 2 9 4 8 7 3 1 不用交换 第一步,校验父节点为1的 第二步,校验父节点为9的 6 2 9 4 8 7 3 1 交换 第三步,校验父节点为2的 6 8 9 4 2 7 3 1 交换 第四步,校验父节点为6的 9 8 6 4 2 7 3 1 交换 第五步,校验父节点为6的 9 8 7 4 2 6 3 1 完成

上图是一个无序树变成大根堆的过程,我们从最后一个父节点开始,从下往上,从右往左遍历所有的父节点,依次校验,那么对于一个个数为n的堆,如何找到最后一个父节点的位置呢?

因为我们的根节点下标为0,所以最后一个节点下标为n-1,那么最后一个父节点的位置为Math.ceil((n-1)/2-1),例如上面的案例中,数组个数为8,那么第一个父节点位置为下标为Math.ceil(7/2)-1=3。对应到树上,也就是1(第一步的时候)。

我们注意第五步,为什么在根节点校验完成后还要继续再校验一次?因为根节点校验完成后,导致右孩子那个单元不满足条件了,因此还要把右孩子纠正过来。这一步很重要,而且是循环纠正的,每纠正一个单元,我们都要再去验证下被交换孩子那个单元的平衡是否被破坏了,如果破坏了,我们还要纠正回来。

交换&重新建堆

把无序堆变成大根堆后,我们就要不断的进行交换根节点和尾节点了,这样的目的其实就是把已经找到的最大的数字给保存起来,同时缩小堆,重新构建,再次交换。

background Layer 1 9 8 7 4 2 6 3 1 第一步,交换根节点和最后节点 交换&缩小堆 1 8 7 4 2 6 3 9 第二步,重新调整成大根堆 交换 8 1 交换 8 4 7 1 2 6 3 9 第三步,交换根节点和最后节点 3 4 7 1 2 6 9 第四步,重新调整成大根堆 8 交换 3 7 交换 7 4 6 1 2 3 第五步,交换根节点和最后节点 9 8 3 4 6 1 2 9 8 7 交换 第六步,重新调整成大根堆 6 4 3 1 2 第七步,交换根节点和最后节点 9 8 7 2 4 3 1 9 8 7 6 第八步,重新调整成大根堆 交换&缩小堆 交换&缩小堆 交换&缩小堆 交换 4 2 3 1 9 8 7 6 第九步,交换根节点和最后节点 交换&缩小堆 1 2 3 9 8 7 6 4 第十步,重新调整成大根堆 交换 3 2 1 9 8 7 6 4 第十一步,交换根节点和最后节点 交换&缩小堆 1 2 9 8 7 6 4 交换 3 第十二步,重新调整成大根堆 2 1 9 8 7 6 4 3 第十三步,交换根节点和最后节点 交换&缩小堆 9 8 7 6 4 3 2 1 完成

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字