算法----堆排序

原创 lronelove 随笔 算法笔记 110阅读 2019-01-28 11:42:52 举报

1. 什么是堆排序?

堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
如下图:

堆排序的性能比较优秀,时间复杂度是O(nlogn)

2. 如何实现堆排序

第一步,实现构造出一个最大堆。

也就是让父节点的值大于左子节点和右子节点的值。
这里有一个数组:

那么它对应的堆结构如下图:

红色标注代表下标,一层层填充。

可以发现:
假设父节点下标是i,那么左子节点下标是2 i + 1,右子节点下标是2 i + 2
于是有:

后面会经常用到交换两个数组元素的一个函数exchange

显然,我们现在的堆并不满足最大堆的性质,比如4的左子节点是14比,比4大。
那么我们怎么处理呢?
我们发现子节点比父节点大的时候,把最大的子节点child和父节点parent交换下位置,这样就可以保持最大堆的性质了。交换之后我们还得看看,parent是否比现在的子节点小,如果小,那么继续交互。
具体代码如下:

好,我们现在已经可以维护最大堆的性质了。但是如何去构建一个最大堆呢?

有一个规律,下标大于节点总数的一半的,都是叶节点,也就是说,它们没有子节点。
那么,我们只需要从0到节点总数的一般去维护最大堆的性质,就可以构建最大堆了。
代码如下:

好,现在我们现在的最大堆就有了。
那么,建成之后的最大堆如下图:

3. 使用最大堆来完成堆排序

我们可以看见,堆顶肯定是最大的那个数。
所以,我们建完堆后,获取堆顶的那个数,然后,移除。
这样就不是最大堆了。但是,我们的子堆都满足最大堆,所以,我们只需要再次维护下堆就可以了。
代码如下:

这样就可以了,结果如图:

完整代码:

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复