Java教程

排序之堆排序

本文主要是介绍排序之堆排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

一、堆的定义

二、建立大根堆（小根堆会得到递减序列）

三、进行排序

代码实现：

小结：

四、堆中插入新元素

五、堆中删除元素

小结：

下一篇：排序之归并排序

一、堆的定义

理解为完全二叉树

二、建立大根堆（小根堆会得到递减序列）

非终端结点编号为n/2向下取整

代码：

三、进行排序

87与堆底元素互换后，发现该堆不是个大根堆，要将该堆调整，将09下沉

调整后

第一趟处理完成

依次处理完堆中所有元素

最后结果：

代码实现：

全部代码：

效率分许：

结论

建堆时间复杂度

排序过程中下沉的时间复杂度

整体来看：

空间复杂度为O(1)

稳定性

不稳定

小结：

四、堆中插入新元素

小根堆为例

在数组最后加入元素13（就是在堆的末尾加上13这个结点）

父结点大于这个新结点就交换依次往上

最后到达

五、堆中删除元素

用堆底的元素代替删除的元素，再让该元素下坠直到无法下坠

不断下坠后

对比次数

下坠中若有两个孩子则对比两次

一个孩子则对比一次

小结：

这篇关于排序之堆排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航