排序算法:堆排序

排序算法:堆排序

 

相关博客:

排序算法:冒泡排序、插入排序、选择排序、希尔排序

排序算法:归并排序、快速排序

排序算法:桶排序、计数排序、基数排序

排序算法:堆排序

十大排序算法小结


一、堆:

1、什么是堆:

堆是一种特殊的树,它满足需要满足两个条件:

(1)堆是一种完全二叉树,也就是除了最后一层,其他层的节点个数都是满的,最后一个节点都靠左排列。

(2)堆中每一个节点的值都必须大于等于(或小于等于)其左右子节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆,我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作“小顶堆”。

2、堆的实现:

用数组来存储完全二叉树是非常节省内存空间的,因为我们不需要存储左右子节点的指针,单纯通过数组的下标,就可以找到一个节点的子节点和父节点。

排序算法:堆排序

从图中我们可以看到,数组中下标为 i 的节点的左子节点,就是下标为 i∗2 的节点,右子节点就是下标为 i∗2+1的节点,父节点就是下标为i/2的节点。

3、堆的核心操作:

(1)往堆中插入一个元素:

我们新插入一个元素之后,堆可能就不满足堆的特性了,就需要进行调整,让其重新满足堆的特性,即堆化(heapify),堆化非常简单,就是顺着节点所在的路径,向上或者向下,对比,然后交换。所以分为两种,从下往上 和 从上往下。

①从下往上堆化:

例如:在已经建好的堆中插入值为“22”的结点,这时候就需要重新调整堆结构,过程如下:

排序算法:堆排序

Java代码实现:

public class Heap {
	private int[] a;//数组,从下标1开始存储数据
	private int n;//堆可以存储的最大数据个数
	private int count;//堆中已经存储的数据个数
	
	public Heap(int capacity){
		a = new int[capacity+1];
		n=capacity;
		count = 0;
	}
	
	//1、插入数据,并从下往上堆化
	public void insert(int data){
		if(count>=n) return;//堆满了
		++count;
		a[count]=data;
		int i = count;
		while(i/2>0 && a[i]>a[i/2]){
			swap(a,i,i/2);
			i=i/2;
		}
	}

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

(2)从堆中删除堆顶元素:

删除步骤:把最后一个节点放到堆顶,然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的,互换两个节点,并且重复进行这个过程,直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法

例如:删除堆顶的“33”结点,删除步骤如下:

排序算法:堆排序

Java代码实现:

        public void removeMax(){
		if(count ==0) return;
		a[1]=a[count];
		--count;
		heapity(a,count,1);
	}

	//2、自上往下堆化
	private void heapity(int[] a2, int n, int i) {
		while(true){
			int MaxPos=i;
			if(i*2<=n && a[i]<a[i*2]) MaxPos=i*2;
			if(i*2+1<=n && a[MaxPos]<a[i*2+1]) MaxPos=i*2+1;
			
			if(MaxPos==i) break;
			swap(a, i, MaxPos);
			i=MaxPos;
		}
	}

一个包含 n个节点的完全二叉树,树的高度不会超过 log2n。堆化的过程是顺着节点所在路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化,所以在堆中插入一个元素和删除堆顶元素的时间复杂度都是O(logn)。


二、堆排序:

1、算法原理:

堆排序是指利用堆这种数据结构进行排序的一种算法。

(1)排序过程中,只需要个别临时存储空间,所以堆排序是原地排序算法,空间复杂度为O(1)。

(2)堆排序的过程分为建堆和排序两大步骤。建堆过程的时间复杂度为O(n),排序过程的时间复杂度为O(nlogn),所以,堆排序整体的时间复杂度为O(nlogn)。

(3)堆排序不是稳定的算法,因为在排序的过程中,存在将堆的最后一个节点跟堆顶节点互换的操作,所以可能改变值相同数据的原始相对顺序。

2、建堆:

(1)第一种是实现思路:借助前面的,在堆中插入元素的思路。将要排序的数组从前往后处理,依次到插入堆中,并且每次都从下往上进行堆化。

(2)第二种实现实现思路:从后往前处理数组,并且每个数据都是从上往下堆化。也就是从二叉树中第一个非叶子节点开始开始堆化,因为叶子节点往下堆化只能自己跟自己比较。如下图:

排序算法:堆排序

排序算法:堆排序

Java代码实现:

        //3、第二种堆化的方法:
	public void buildHeap(int[] a,int n){
		for(int i=n/2;i>=1;--i){
			heapity(a,n,i);
		}
	}
	
	//2、自上往下堆化
	private void heapity(int[] a, int n, int i) {
		while(true){
			int MaxPos=i;
			if(i*2<=n && a[i]<a[i*2]) MaxPos=i*2;
			if(i*2+1<=n && a[MaxPos]<a[i*2+1]) MaxPos=i*2+1;
			
			if(MaxPos==i) break;
			swap(a, i, MaxPos);
			i=MaxPos;
		}
	}

3、排序:

(1)建堆:建堆结束后,数组中的数据已经是按照大顶堆的特性组织的。数组中的第一个元素就是堆顶。

(2)取出最大值(类似删除操作):将堆顶元素a[1]与最后一个元素a[n]交换,这时,最大元素就放到了下标为n的位置。

(3)重新堆化:交换后新的堆顶可能违反堆的性质,需要重新进行堆化。

(4)重复(2)(3)操作,直到最后堆中只剩下下标为1的元素,排序就完成了。

排序算法:堆排序

Java代码实现:

        //4、排序,n表示数据的个数。
	public void sort(int[] a,int n) {
		buildHeap(a,n);
		int k=n;
		while(k>1){
			swap(a, 1, k);
			--k;
			heapity(a,k,1);
		}
	}

 

 

本篇博客主要参考《极客时间》王争的《数据结构与算法之美》专栏第28节。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114617.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 安全帽佩戴识别 安全帽识别 安全帽检测 yolo安全帽识别 ssd安全帽识别 fastertcnn安全帽识别 retinanet安全帽识别 lbp安全帽识别 cnn安全帽检测 神经网络安全帽识别

    安全帽佩戴识别 安全帽识别 安全帽检测 yolo安全帽识别 ssd安全帽识别 fastertcnn安全帽识别 retinanet安全帽识别 lbp安全帽识别 cnn安全帽检测 神经网络安全帽识别

  • 什么是QT[通俗易懂]

    什么是QT[通俗易懂]QT是什么?它能做什么?Qt是一个1991年由QtCompany开发的跨平台C++图形用户界面应用程序开发框架。它既可以开发GUI程序,也可用于开发非GUI程序,比如控制台工具和服务器。简单来说,QT可以很轻松的帮你做带界面的软件,甚至不需要你投入很大精力。QT学习需要避免的坑QT分为4.0版本和5.0版本他们之间的差别很大,不通用!!!不通用!!!不通用!!!所以要么你学习4.0要么你学习5….

  • java 零拷贝_java深拷贝

    java 零拷贝_java深拷贝在传统的数据IO模式中,读取一个磁盘文件,并发送到远程端的服务,就共有四次用户空间与内核空间的上下文切换,四次数据复制,分别是两次CPU数据复制,两次DMA数据复制。零拷贝指在进行数据IO或传输时,数据在用户态下经历了零次拷贝,并非不拷贝数据。通过减少数据传输过程中内核缓冲区和用户进程缓冲区间不必要的CPU数据拷贝与用户态和内核态的上下文切换次数,降低CPU在这两方面的开销,释放CPU执行其他任务,更有效的利用系统资源,提高传输效率,同时还减少了内存的占用,提升应用程序的性能

  • android的开机动画,设置安卓开机动画、开机logo

    android的开机动画,设置安卓开机动画、开机logo我们要修改的是system>media文件夹下的bootanimation.zip(手机开机动画)这个文件先来讲讲这个文件结构:该zip解压后得到两个文件,第一个目录存放了开机时播放的图片(图为佳域G3原厂的动绘图片包),见下图:图片编号001,002,…….010这些是用来控制图片播放顺序的。第二个desc.txt的文本文档存放的数据和文字用来控制播放图片的速度(帧速)和播放方…

  • 变量命名神器Codelf

    变量命名神器Codelf网站首页

  • 如何编写单元测试用例

    如何编写单元测试用例 一、单元测试的概念  单元通俗的说就是指一个实现简单功能的函数。单元测试就是只用一组特定的输入(测试用例)测试函数是否功能正常,并且返回了正确的输出。  测试的覆盖种类  1.语句覆盖:语句覆盖就是设计若干个测试用例,运行被测试程序,使得每一条可执行语句至少执行一次。  2.判定覆盖(也叫分支覆盖):设计若干个测试用例,运行所测程序,使程序中每个判断的取真分支和取假分支至少执行一次。  3.条件…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号