堆排序-程序员宅基地

技术标签: 算法  排序  

1、首先了解堆是什么

堆是一种数据结构,一种叫做完全二叉树的数据结构。

2、堆的性质

这里我们用到两种堆,其实也算是一种。

大顶堆:每个节点的值都大于或者等于它的左右子节点的值。

小顶堆:每个节点的值都小于或者等于它的左右子节点的值。

如上所示,就是两种堆。

如果我们把这种逻辑结构映射到数组中,就是下边这样

9 5 8 2 3 4 7 1
1 3 5 4 2 8 9 7

这个数组arr逻辑上就是一个堆。

从这里我们可以得出以下性质(重点)

对于大顶堆:arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

对于小顶堆:arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

3、堆排序的基本思想

了解了以上内容,我们可以开始探究堆排序的基本思想了。

堆排序的基本思想是:1、将带排序的序列构造成一个大顶堆,根据大顶堆的性质,当前堆的根节点(堆顶)就是序列中最大的元素;2、将堆顶元素和最后一个元素交换,然后将剩下的节点重新构造成一个大顶堆;3、重复步骤2,如此反复,从第一次构建大顶堆开始,每一次构建,我们都能获得一个序列的最大值,然后把它放到大顶堆的尾部。最后,就得到一个有序的序列了。

假设给定的无序序列arr是:

4 5 8 2 3 9 7 1

1、将无序序列构建成一个大顶堆。

首先我们将现在的无序序列看成一个堆结构,一个没有规则的二叉树,将序列里的值按照从上往下,从左到右依次填充到二叉树中。

 

根据大顶堆的性质,每个节点的值都大于或者等于它的左右子节点的值。所以我们需要找到所有包含子节点的节点,也就是非叶子节点,然后调整他们的父子关系,非叶子节点遍历的顺序应该是从下往上,这比从上往下的顺序遍历次数少很多,因为,大顶堆的性质要求父节点的值要大于或者等于子节点的值,如果从上往下遍历,当某个节点即是父节点又是子节点并且它的子节点仍然有子节点的时候,因为子节点还没有遍历到,所以子节点不符合大顶堆性质,当子节点调整后,必然会影响其父节点需要二次调整。但是从下往上的方式不需要考虑父节点,因为当前节点调整完之后,当前节点必然比它的所有子节点都大,所以,只会影响到子节点二次调整。相比之下,从下往上的遍历方式比从上往下的方式少了父节点的二次调整。

那么,该如何知道最后一个非叶子节点的位置,也就是索引值?

对于一个完全二叉树,在填满的情况下(非叶子节点都有两个子节点),每一层的元素个数是上一层的二倍,根节点数量是1,所以最后一层的节点数量,一定是之前所有层节点总数+1,所以,我们能找到最后一层的第一个节点的索引,即节点总数/2(根节点索引为0),这也就是第一个叶子节点,所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢?这个计算方式仍然适用,当我们从上往下,从左往右填充二叉树的过程中,第一个叶子节点,一定是序列长度/2,所以第一个非叶子节点的索引就是arr.length / 2 -1。

现在找到了最后一个非叶子节点,即元素值为2的节点,比较它的左右节点的值,是否比他大,如果大就换位置。这里因为1<2,所以,不需要任何操作,继续比较下一个,即元素值为8的节点,它的左节点值为9比它本身大,所以需要交换

交换后的序列为:

4 5 9 2 3 8 7 1

因为元素8没有子节点,所以继续比较下一个非叶子节点,元素值为5的节点,它的两个子节点值都比本身小,不需要调整;然后是元素值为4的节点,也就是根节点,因为9>4,所以需要调整位置

交换后的序列为:

9 5 4 2 3 8 7 1

此时,原来元素值为9的节点值变成4了,而且它本身有两个子节点,所以,这时需要再次调整该节点

交换后的序列为:

9 5 8 2 3 4 7 1

到此,大顶堆就构建完毕了。满足大顶堆的性质。

2、排序序列,将堆顶的元素值和尾部的元素交换

交换后的序列为:

1 5 8 2 3 4 7 9

然后将剩余的元素重新构建大顶堆,其实就是调整根节点以及其调整后影响的子节点,因为其他节点之前已经满足大顶堆性质。

交换后的序列为:

8 5 7 2 3 4 1 9

然后,继续交换,堆顶节点元素值为8与当前尾部节点元素值为1的进行交换

交换后的序列为:

1 5 7 2 3 4 8 9

重新构建大顶堆

交换后的序列为:

7 5 4 2 3 1 8 9

继续交换

交换后的序列为:

1 5 4 2 3 7 8 9

重新构建大顶堆

构建后的序列为:

5 3 4 2 1 7 8 9

继续交换

交换后的序列为:

1 3 4 2 5 7 8 9

重新构建大顶堆

构建后的序列为:

4 3 1 2 5 7 8 9

继续交换

交换后的序列为:

2 3 1 4 5 7 8 9

重新构建大顶堆

构建后的序列为:

3 2 1 4 5 7 8 9

继续交换

交换后的序列为:

1 2 3 4 5 7 8 9

重新构建大顶堆

构建后的序列为:

2 1 3 4 5 7 8 9

继续交换

交换后的序列为:

1 2 3 4 5 7 8 9

此时,序列排序完成。以上就是整个堆排序的逻辑。

4、堆排序的代码实现(java版本)

public class HeapSort {

	public static void heapSort(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		int len = arr.length;
		// 构建大顶堆,这里其实就是把待排序序列,变成一个大顶堆结构的数组
		buildMaxHeap(arr, len);

		// 交换堆顶和当前末尾的节点,重置大顶堆
		for (int i = len - 1; i > 0; i--) {
			swap(arr, 0, i);
			len--;
			heapify(arr, 0, len);
		}
	}

	private static void buildMaxHeap(int[] arr, int len) {
		// 从最后一个非叶节点开始向前遍历,调整节点性质,使之成为大顶堆
		for (int i = (int)Math.floor(len / 2) - 1; i >= 0; i--) {
			heapify(arr, i, len);
		}
	}

	private static void heapify(int[] arr, int i, int len) {
		// 先根据堆性质,找出它左右节点的索引
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		// 默认当前节点(父节点)是最大值。
		int largestIndex = i;
		if (left < len && arr[left] > arr[largestIndex]) {
			// 如果有左节点,并且左节点的值更大,更新最大值的索引
			largestIndex = left;
		}
		if (right < len && arr[right] > arr[largestIndex]) {
			// 如果有右节点,并且右节点的值更大,更新最大值的索引
			largestIndex = right;
		}

		if (largestIndex != i) {
			// 如果最大值不是当前非叶子节点的值,那么就把当前节点和最大值的子节点值互换
			swap(arr, i, largestIndex);
			// 因为互换之后,子节点的值变了,如果该子节点也有自己的子节点,仍需要再次调整。
			heapify(arr, largestIndex, len);
		}
	}

	private static void swap (int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

5、复杂度分析

因为堆排序无关乎初始序列是否已经排序已经排序的状态,始终有两部分过程,构建初始的大顶堆的过程时间复杂度为O(n),交换及重建大顶堆的过程中,需要交换n-1次,重建大顶堆的过程根据完全二叉树的性质,[log2(n-1),log2(n-2)...1]逐步递减,近似为nlogn。所以它最好和最坏的情况时间复杂度都是O(nlogn),空间复杂度O(1)。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_28063811/article/details/93034625

智能推荐

ADB投屏_Android跨平台投屏软件(无需root)--scrcpy-程序员宅基地

文章浏览阅读1.8k次。之前一直使用 Chrome 的一个插件「Vysor」进行 Android 手机的投屏,但是有码率限制,高码率需要付费,最近发现一个更好的继任者「scrcpy」,就来推荐一下。本文将以 Mac 为例进行配置和使用 scrcpy,其他系统请参考官方文档,要求有一定的技术动手能力,觉得过于复杂的用户推荐使用「Apower Mirror」(使用简单,支持 Android 和 iOS)。项目介绍做过 And..._adb 投屏

【Python学习】 - sklearn学习 - 数据集分割方法 - 随机划分与K折交叉划分与StratifiedKFold与StratifiedShuffleSplit_from sklearn.model_selection import kfold-程序员宅基地

文章浏览阅读1w次,点赞9次,收藏49次。一、随机划分import numpy as npfrom sklearn import datasetsiris = datasets.load_iris()X = iris.datay = iris.target# 1)归一化前,将原始数据分割from sklearn.model_selection import train_test_splitX_train,X_tes..._from sklearn.model_selection import kfold

Mybatis一对一、一对多、多对多查询。+MYSQL-程序员宅基地

文章浏览阅读9.8k次,点赞17次,收藏81次。场景:使用三张数据表:student学生表、teacher教师表、position职位表一个学生可以有多为老师、一位老师可以有多个学生、但是一个老师只能有一个职位:教授、副教授、讲师;但是一个职位可以有多个老师:例如教授可以多人这里则产生了:一对一关系,从老师角度:老师对职位一对一一对多关系,从职位角度:职位对老师一对多多对多关系:查找被教授教导的所有学生(首先职位对..._"

自动化运维-centos 8 kickstart系统批量部署_centos8 ks-程序员宅基地

文章浏览阅读2.8k次。自动化运维-centos 8 kickstart系统批量部署了解kickstartwhat’s kickstartkickstart 是使用一个标准的站点为一些机器安装统一配置的linux 操作系统。kickstart的配置文件的获得方式:手动写入使用GUI system-config-kickstart 工具使用标准的Red Hat安装程序Anacondaanaconda-ks...._centos8 ks

ImmutableMultiDict转成dic类型(Python)-程序员宅基地

文章浏览阅读1.8w次。Flask中常见的数据类型处理问题项目常见的从前端通过Ajax返回的数据,是ImmutableMultiDict类型的,我们要处理成dic类型然后存入后台数据库。各种百度搜索,都是骗子,不如自己捣鼓。前端Ajax取数据View.py里面的处理方法a = request.values #把Ajax中的数据取出来 print(a) #输出一下,看是什么类型,Imm..._immutable

(1)Hadoop 的第一个程序 WordCount 理解_为啥第一个写word count-程序员宅基地

文章浏览阅读88次。Hadoop 的第一个程序 WordCount 理解map and Reduce 相关概念Mapmap 负责将自己区块数据, 做简单拆分, 成一个map, 这个map 是不去重的, 会在map 后面最加值, 让数据分组比如两个 机器的两个mapmachine1:# 以下数据是machine1 hdfs 区块的数据hello hello hello// 这是machine 1 的 context[ {"hello" : 1}, {"hello" : 1}, {"hello_为啥第一个写word count

随便推点

MyBatis3 DynamicSql风格语法使用指南_selectstatementprovider-程序员宅基地

文章浏览阅读1.8w次。MyBatis3-DynamicSql风格语法使用指南转载请注明出处:https://www.jjput.com/archives/dynamicsql主要演示DynamicSql风格代码如何使用,基本能应对大部分使用场景。DynamicSql基本介绍点我查看。本文主要沿着增、删、改、查的思路进行介绍,尽量涵盖日常使用所需。我这里还是要推荐一下大家看官方文档,尽量有问题先找官方文档教程,除非写的跟屎一样,但大概率不会。本次使用的是mybatis-dynamic-sql1.2.1版本<!--_selectstatementprovider

Java8特性总结(二)Lambda表达式,函数式接口,方法引用_返回值是function<integer,string>的方法-程序员宅基地

文章浏览阅读3.4k次。Lambda表达式,函数式接口,方法引用_返回值是function的方法

LRN层的实现-程序员宅基地

文章浏览阅读1.8w次。版权声明:本文为卜居原创文章,未经博主允许不得转载。卜居博客地址:http://blog.csdn.net/kkk584520LRN全称为Local Response Normalization,即局部响应归一化层,具体实现在CAFFE_ROOT/src/caffe/layers/lrn_layer.cpp和同一目录下lrn_layer.cu中。该层需要参数有:norm_lrn层

win10安装.NET 3.5报错 错误代码0X80070005 的解决方案_.net3.5错误代码0x80070005-程序员宅基地

文章浏览阅读1.2k次。然后再使用dotnetfx35.exe安装,最好以管理员方式运行。使用这个工具打开Windows更新。_.net3.5错误代码0x80070005

Image Style Transfer Using Convolutional Neural Network_image style transfer using convolution neural netw-程序员宅基地

文章浏览阅读560次。转载自:http://blog.csdn.net/gavin__zhou/article/details/53144148今天这篇是关于neual art的,也就是style transfer算法; 文章来源: A Neural Algorithm of Artistic Style, CVPR2015 Image Style Transfer Using Convolut_image style transfer using convolution neural network

基于AO/AE获取要素信息_ao怎么获取选中的group-程序员宅基地

文章浏览阅读1.5k次。基于AO/AE获取要素信息1、基于AE获取要素简单信息 Private Sub AxMapControl1_OnMouseDown(ByVal sender As Object, ByVal e As ESRI.ArcGIS.MapControl.IMapControlEvents2_OnMouseDownEvent) Handles AxMapControl1.OnMouseDown_ao怎么获取选中的group

推荐文章

热门文章

相关标签