Jack Frost

数据结构与算法–堆排序(Java描述)

我将陆续把我以前学习以及现在复习数据时,遇坑特久,理解特慢的一些算法写出来具体过程。记录总结自己的思路。


文章结构:(1)概念;(2)算法分析以及复杂度;(3)详解大根堆。


一、概念:

(1)堆是一棵顺序存储的完全二叉树。

(2)大根堆与小根堆

其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆。

其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆。

(3)逻辑结构与存储结构:

这里写图片描述

(4)公式计算孩子结点以及父结点:

拿结点i为例子:它的父结点就是:(i-1)/2。 而它的左右子结点就分别是:2i+1和2i+2。如第0个结点左右孩子结点就是1和2。

(5)堆排序总体流程:堆调整+堆排序

二、算法分析以及复杂度

这里写图片描述

空间复杂度:

空间复杂度:o(1);

堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树,而完全二叉树通常采用顺序存储方式。

时间复杂度:

建堆:o(n),每次调整o(log n),故最好、最坏、平均情况下:o(n*log2n);

算法稳定性:

一种不稳定的排序方法。

因为在堆的调整过程中,关键字进行比较和交换所走的是该结点到叶子结点的一条路径,

因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

三、详解大根堆:

(1)图解(有两张图是他人的,不过很明确详细):

建堆,以及调整堆

这里写图片描述

堆排序

这里写图片描述

核心代码:并结合图解析:

下面是我为了理解方便而打了几个System出来的结果

这里写图片描述

文字解析“调整”过程

(1)最后一位是0,它的父结点是2,HeapAdjust方法中的parent指向的是最后结点的父结点,因父结点大于左右子结点,所以直接结束循环。对比2的child=length,结束第一次调整。

(2)现在调整轮到倒数第二个数5的父结点调整。进入HeapAdjust方法,parent一开始指向的是5,循环检查时发现5的子节点大于它自己,就实行了交换!!并且!!把parent指向了那个子结点以便继续向下调整,进行大根堆调整,把大数丢上面去。继续判断parent指向子结点后,与length相等,结束第二次调整。

文字解析“排序”过程

这里写图片描述

过程:其实就是每次调整都把最大数丢到了最上面去了,所以我们每次只要把最大数与最后面的那个数交换,然后每次调整把剩余位置的最大数丢上面去,再与最后的数交换,并不断缩小剩余位置区间,即可完成排序。

完整的demo代码:


参考博客:http://www.cnblogs.com/jingmoxukong/p/4303826.html

源码下载:数据结构与算法–大礼包(含全部基本知识解析和demo)

好了,数据结构与算法–堆排序(Java描述)讲完了。本博客是我最近复习的一个算法,复习的时候遇坑较深,发现自己有点难理解了,就写博客记录分享给大家,接下来每遇一个大坑,而别人博客讲得不完善不够好的,我都会记录总结下来,分享经验给大家。欢迎在下面指出错误,共同学习!!你的点赞是对我最好的支持!!

更多内容,可以访问JackFrost的博客

码字很辛苦,转载请注明来自JackFrost《数据结构与算法–堆排序(Java描述)》

One response to “数据结构与算法–堆排序(Java描述)”

  1. 老李 says:

    感觉你懂得好多啊

Leave a Reply

Your email address will not be published. Required fields are marked *