00:00
各位同学,我们来实现一把这个堆排序好的,那么我们现在怎么来写呢?我还是把这个堆排序放在脆这个包包下面,因为它是我们数的一个应用,对不对?好,我先在这写一下。那么首先呢,我们写一个have。堆手。没问题吧,对,少。Short,然后呢,我在这里呢,先把这个数组写出来,因为待会呢,我们要操作的数组就它。这个数组。写上。呃,数组的我们我们就以这个为例哈,四六。46859,这样待会呢,我们可以比对好,有了它过后呢,我们首先写一个方法,就是就是完成一个堆排序的方法。编写一个堆,注意听啊,堆排序的方法,那这个堆排序的方法呢,我们写个public static void OK,名字叫help。
01:07
那你在堆排序的时候,你给我传一个什么呢?各位你把一个数组传给我就可以了。我就帮你完成这个堆排序,好,我这里打一句话。这叫什么呢?堆排序。堆。没问题吧,堆排序。大家都知道这个堆排序里面最核心,最核心的代码是哪一部分。是不是就是把你的一个指数调整成一个大顶,对药啊,当然我前提要说清楚啊。因为我调成大顶堆还是小顶堆,是跟你这个要求有关系的,这样写啊,要求要求将数组进行升序。顺序排列,呃,那既然是正序排列,我肯定做的是大顶堆了,因为刚才我我讲的也是这样一个顺序,所以说。我们这个堆排序里面最核心的就是你怎么把一个。
02:05
就这一步吧,说再直接一点,怎么把这一个。把这一个。呃,给的一个宿主。把这个给了一个数组一堆,呃,以大顶堆的形式把它重新的给构建起来,是这样子的吧,说的再直接点一点,就是说我们怎么样完成这个任务。好,那现在呢,我先来写最核心的代码。我先把这个代码方法写出来啊,这个方法是干什么呢?我先写清楚,将一个将一个呃。嗯,将一个数组吧。将一个数组,但是这个数组呢?它其实对应的是一个二叉树。是不是将一个数组,呃,就是它对应的二条数调整成,注意听这句话有点不好理解,调整成。一一颗,一个什么呢?一个大顶堆。
03:02
大。大顶推啊大顶推,别写错了,顶推。领队。得得,为一堆好。那现在就写这个方法了,那我写public,注意听讲啊,这个有点难,Public VO sta static。那么我就写一个方法,叫adjust。Just是调整的意思,调整对。好不好,那调整对的时候,你肯定要把这个数组给我,你不给我数组不行,第二个你要把这个长度给我,哎,对长度还还是子啊,还有个I,还有一个长度,数度的长度给我一下。AG,那首先呢,我我对这个方法做一个简单的说明,Public。贸易的static。好,我们这边没有写完啊,没有写完那么。
04:01
那么现在的问题是。调整一下。好,现在呢,我们来做一个这样的,这个地方也写了小问题啊,我现在确定一下这几个变量,就是参数的含义,先把这个定清楚,不然待会大家听不懂,这个数组呢,就是待调整的,待调整的这个数组。没问题吧?I,注意听这句话,I是表示什么呢?这点很重要。I是表示,表示非。最近这句话非叶子节点。这个非叶子节点的。这个在数组中的,在数组中的那个索引。所以好,呃,那么这个地方呢,嫩是表示什么呢?哎,这个嫩是表示对对多少个多要注意啊,多少个元素进行调整。
05:01
因为你在调整的过程中,大家有没有发现他在不停的减少,你第一次调整完毕过后,交换完了过这个酒呢,就已经搞定了,就离开他了,那下一次是不是要减少一个元素再调整是不是,所以说我这地方写上。表示多少个元素调整,那么在那是在逐渐减少。那是在我把这个全屏一下,嫩是在逐渐的减少,这一点大家一定要有一个认识啊,减减少。没有任何问题吧?没有任何问题,好,嗯,那现在我们要说这个方法它的作用是干什么,就是先这个这个方法的功能是什么呢?这个方法的功能是完成一个这样的任务,他要完成什么呢?注意听啊,完成当我们传递了,当我们。就是那这样说啊,他的任务是要完成将。
06:02
将什么呢?将乙。以这个,呃,I就是一,就是这个I是一个啊,这个不好描述,就是完成将以I指指向的I对应的这个非叶子节点非叶子。非叶非叶子节点的这个数,这个数调调整成。调整成大。顶对,到顶对。好,这样有点不好理解,我举个例子你们就明白了,比如说这个数组啊,我们假设你传进来是这个数组,举个例子啊,大家一下就明白了。如好,我第一次大家知道我我第一次调,第一次进行这个调整的时候,是不是是不是他传过来的。这个非叶子节点的索引是医药。
07:00
能理解我的意思吗?你第一次调整肯定你最左边最最后的一个非叶节点,这个下边唯一嘛,所以说相当于是这种感觉,这样大家听起来就轻松了,比如说这个I呢,它等于等于一的情况下。它传进来了,它传进来过后呢,我经过这个方法的处理。我经过这个方法的处理,我会得到一个怎样的数组呢?我会得到。注意听哦,得到这样一个数组。得到哪个数组呢?得到这一次以这个六,六为这个非叶子节点调整过后的一个。呃,就是那个,嗯,那个结果,那个结果就应该是哪一个呢,同学们。那个结果就应该是四这个啊,49856。明白意思吧,就是说你把这个呃,这个节点的位置,这个VS节点的索引给我过后,我就相当于把以这个这个VS节点为这个为这个树的,为这个树的呃这么一个呃这这么一个结构调整成一个大顶堆,当然这还是局部的啊。
08:13
因为你在调整的时候呢,总是从最。底层开始调整,调整完了过后再去调整这个四为非意节点的,呃,一个大顶堆是这样子,也就是说你如果我传的是一个I,他最后返回来结果应该是什么呢?就是498。五六。哦,49856好,我这样写到这就49856啊这个这样大家应该会稍微好一点是。是。九。856好,假设我们传的是I,它就会得到这个,那这个调整了以后呢,我们可以继续调用这个I just help,再给他传一个什么呢?再给他传一个零。因为你下次调整的时候呢,就是以这个为非叶节点来调整,就会调整成九。
09:06
四。OK。啊,应该调成什么啊,应该调成这个了,再一次给的话就调成968。五四明白我的意思吧,啊,这个大家你就说下一次再调用。如果我们再次调用这个不好理解啊,注意听再次调用我们这个adjust。好,这个时候我们传入的应该是什么呢?传入的是这个I等于零了。对不对,这个时候调整完了过后呢,相当于是在这个基础上进行调整。调整成这个样子了,调整成真正的,真正的第一颗,真正的第一颗大顶堆。东西了,就变成96854了啊,96854了。九就变成九。
10:00
685。是好,这是我们这个方法要。完成的功能,也就是说你给我一个I。你给我传一个I,这个I是对应那个非叶节点,然后呢,我就我就必须要把以这个I为非叶节点的一棵树调成大顶堆,那么你调完了过后呢,这个I继续往上走,因为你是从左到右,从下到上嘛,再调,最终不停的调整呢,最后就把这个树调整成一个。大顶堆了,现在这个就是一个大顶堆是不是啊,只是你还没交换好,这是这是他要做的事情啊,那下面明白这个道理过后呢,就比较简单了,来老师给他写一下temp,我先把当前这个词解呃保留下来。这个是干什么先?先取出,当前先取出。当前元素的值保存在。
11:02
保存在一个临时变量。保存在临时变量,这个理解吗?待会我要用好,现在我开始找位置了,开始调整。开始调整哦,这个地方要注意听啊,For循环。首先我们知道你在调整的时候其实是找I。它对应的浊子节点。是不是这个道理?那么I对应的左止节点应该是哪一个呢?是,是I乘以。二再加一个一。明白吧,K如果小于嫩识,因为你呢是对认识个元素进行调整,所以说只要K它小于认识,我就可以做,然后下一次。这个K呢,就变成了这个,我不知道大家能不能理解。大家看一下就是不是有点懵了,这个K代表的是以I。为非叶子节点的浊子节点。
12:03
左止节点,那下次再调的话呢,又调的是它下面的左止节点。明白这意思吧,好,这边我要写清楚啊,说明一把。说明一呢,就是这个这个K这句话是它是这个K指向的啊是哪个呢?是I这个节点的着。左子。子节点好,明白这个道理就行了,那明白这个道理过后,我们要在这边找一个最这个for循环,要完成一个什么事情呢,就要找到。最大值,并且把它放在适当的位置,好,现在我们开始写了啊,If,如果我们K。加一。K加一在小于嫩子的情况下,说明它还没有还没约见,因为K加一呢,呃,是要是要去判断它的,嗯,这样这样写啊,这个条件我我先写个别的条件大家就就好看了,为什么要有这个条件,如果K小于二,K加一问,呃,哪个同学告诉我这句话什么意思?
13:07
如果RK小于K加一,说明什么问题?说明什么说明。说明什么呀,大家想想说明这个这个镯子节点。卓直接着。着子节点。嗯,又是这个左。子节点啊子节点。它的值干什么小于右子节点的值。右。又指。节点的值,这个能理解吗?因为你RI这个K指向左侧节点,K加一显然就是你这个I的右侧节点,如果这个条件满足的话,说明你左侧节点值小于右右子节点的值,好在这种情况下,我们就让这个K指向右子节点。
14:02
能理解吗?因为你K加加了嘛,那么K呢,就指向。因为你你现在要做的事情,要找一个最大值,是不是K就指向。右。指。节点好,但是这个条件,因为你在做这个事情的时候,你首先要满足K加一,它是要小于认识的,如果K加一它不小于认识,那说明已经没有必要再去比较了,不然的话,你的效率很会很低的,说这个K呢,一定要让他做这个认识,其实你不加这个条件呢也可以,但是效率会降低,所以这个条件一定要加上。好,这个就完成了。对吧,也就是说这句话在找我这个I的右子节点大还是左子节点大。好,那现在完了,过后我就做一个判断了吗?好,R,如果,如果RK各位大于吞搏说明什么问题?因为你现在这个K呢,已经指向了左,左子节点或者右子节点那个最大的指,那如果说你这个左,你你下面这个子节点还大于这个负节点,是不是还要还要进行这个处理啊,就说如果子节点子节点。
15:15
大于。大于什么呢?大于这个负节点。负节点,为什么是负节点呢?因为你刚才已经把这个I放在temp了。说明你下面的子节点比你还大,那应该按照我们大顶推是不是应该进行这个处理啊,那怎么处理呢?Very简单,你把这个。啊,你把这个二位注意看啊,K交给I。也就是说,你相当于把大的这个地方交给了放往上移动了,同时有一个动作很重要,这个动作非常的重要。这个动作是干什么呢?这句话就是。我我写个注释啊,把较大的较大的值干什么呢,付给当前。
16:05
哎,当前这个节点。然后干什么呢?然后让I,让I指向K。继续注意听啊,继续循环比较。大家能理解吧,也就是说你这次完了过后没有完,你因为有可能它下面还有这个K,下面还有它还有左指数或者是右指数是不是,当然你你这你这个地方实际上是以左子节左指数来走的左指数,因为我通过左指数也就能找到他的右子节点,所以说我没必要再去左幼柚子,柚子节点再去玩一把,因为你看这。是不是我在这个地方已经考虑到的它的左右节点,那也就是说这个地方呢,就是。把这个调整,那如果说各位同学。这个条件不满足,说明RK。它干什么呢?小于等于,那这个事情就拉倒了,就break了。
17:03
就break了,就是这个事情我们就结束了,但是老这个地方特别不好理解,同学们为什么你敢break呢?说老师那不对呀,你要这么break的话,那假如他的这个地方特别不好理解啊,那我为什么敢break,你们知道吗?因为。对,很多人会这样想说,老师那你不对,因为你在进行这个比较的时候,你不,虽然你虽然你是看还是看这个图,虽然你只能你现在确实是可以判断,比如说以这个点啊。你这个点,你你敢判断五和九的关系。比如说九确实大于五,你你你找到最大的,但是你怎么敢保证,你怎么敢保证五下面没有呢。五下面的关系谁大谁小呢?你凭什么敢break呢?大家知道为什么我敢吗?我敢break的原因是因为我在进行这个处理的时候,其实我是,我是怎么走的呀?
18:03
是不是我在走的时候,我是这样子走的,是从左至右,从下至上调整的。那也就是说,其实我只要直接比较他的。左右直接点就行了。是不是这个道理,所以我这样就就敢break的原因,因为你调整的时候,其实你原先下面那个节点的下面的其实你已经调整过了,你只要跟他的这个这个左右比较就行了,明白这意思吧,好没关系啊,这这看不懂,我们待会再再debug一下就行了,好整个这个循环结束以后说明什么问题,说明你已经注意听啊,当整个这个for循环结束以后,其实你已经把以I。为这个。以I为这个指数的,呃,这这条数已经把最大的数已经放在这个顶上了,明白这意思吗?啊,这点大家一定要清楚啊,这是这是当注意听,当for循环结束后,For循环结束后,我们已经。
19:07
已经将。将什么呢?将以以I为。为不节点的这棵树。数的最大值放在了,放在什么放在了。你这个挨这个挨,挨原先的位置。因为这个爱的过程它还在调整啊,以爱为负极的这个最大值放在了最最顶上。最顶上最顶。是不是?也就是说,你已局部把这棵树调成一个大顶堆,但是注意啊,是局部啊,注意婷是局部的。你不能说我我已经把所有的调整,只是这个局部,什么叫局部呢?就是你你把以I为这个负节点的这这个这个数的最大值调调整到上面去了。
20:01
仅此而已。好,仅此而已,但是我要问大家一个问题,当我这个循环结束以后,请大家思考此时此刻这个I。还是原来你传进的M,假设以零为为例,比如说我们第一次传的是这个一,请问你调整完了这个这个这个这个I还是一吗?不是一了,这个时候这个I呢,其实指向当前这个节点,因为你总是把K给到I的。是不是也就是说现在你要做一件事情干什么呢?加一个这个动作就可以了。这个地方也不好理解啊,同学们,Temp这句话是将将temp负值值放到。最终的位置就是呃,调整过后的位置,调整后的位置。好,这样个代码我讲完了,可能有些同学对这个代码完全不能理解。啊,因为你是有点难是有点难哦,那我现在这样子,同学们,我举个例子,大家看看呃能不能呃能不能理理解一下啊。
21:08
好,你我们就就以这个为例,以以以这段代码为例,给大家来再做一点简简单的说明,好同学们,我把这个呢拿到这来。我把这个拿到这来啊。大家看一下我我这段代码会运行成怎样一个情况,然后呢,我把。我把这棵树。我把这个也拿过来啊。这是我们最先前的情况,我们来针对这个代码跑一下,看看大家能不能理解的更清晰一点。好,首先大家看,当我要去处理第一个六这个节点的时候呢,我调用的形式应该是这样子的address啊,我这样直接写啊,这个时候就应该是这个数组,这个数组呢应该是是。六。
22:00
八。五九没问题吧,好,呃,数组是这个,然后呢,你这个I应该传的是几呢?I传的是一。好,那是呢,那是你传的肯定就是这这里面的111个数据了啊,这个我就不去不去管它了,好因为这个一时半会咱们用不上,好现在呢,我们开始走代码。做代码同学们,我们走一圈大明的首先。我我先大家看,我这里画个图,首先我让temp大家看啊,我让temp的值是A2是几呢?就是六存起来了。紧接着呢。K等于I加二加一,那么我问大家,这个时候K等于多少?KI加二加一,那就是就三倍。是不是三就是这个五,是不是这样子,那K小于N。K肯定要小于这个认识的,因为我这个认认识呢,是相当于是对这个进行一个便利,所以说K小于这个认识,待会我会把这个认识写出来,小于他,小于他的情况下来我们看。
23:06
K加一也要小于认识,因为你刚开始这个认识比较大的嘛,好好因为你整个认识你你刚开始的时候应该是几啊,应该是123455个是吧,那肯定你你一个还没确定这个,那子肯定是比较大的,好K加一是是小于这个,那那就是。呃,那就是A4小于五成立,小于五成立过后,我们看RK小不小于RK加一呢,大家看RK。RK这个注意听啊,RK呢,其其实它是五五和这个九比较谁大谁小。显然九大,九一旦大化呢,让这个K往后面移动一下,就是相当于K变成了四。指向这个。呃,只讲这个,我这边也可以画一根线啊,这个有点不好理解,所老师一边在画图一边在讲啊,因为堆排序没有几个书讲的非常的清晰,就是都能写,但是呢,不一定都知道为什么,好,此时此刻这个执行它了,下面我们继续走下,这个也执行了,好RK大于temp吗?
24:16
LK是几啊OK现在是九九大于几ten不是六大于它成立,成立的话呢,就让这个RK这个这里面的值付给r v ii现在是几S1。I,现在是不是一啊,同学们。I现在是不是等于一,是等于一,于是这句话呢,就把RK的值付给了I,那也就是说这个六就变成了几呢?呃,我这个六变成九了。我写到这来啊。也就是说现在这个六变九了,各位同学能理解吧?6A5,我写到这六变成九了。能理解啊好,变成九以后,然后I指向这个K,那I指向K,其实I就变成四了,也就现在I让这个I指向你这个当前这个节点,明白吧,现在是不是有点有点清晰了。
25:05
是不是有点清晰了,好,那这个时候我们又去玩。为什么我要去求玩呢?因为我我觉得可能下面还有,但这个时候不一定呢,因为K已经等于22444加二等于九九早就不再小于,它就退出了,因为这个调整就相当于这两个调整就结束了,调整结束过后退出这个for循环,注意看最后一句话,Temp现在是六。I是几呀,I是四,是不是保持上面的这个节点,那么也就是说把六给到我们这个二位四,那相当于这个九就变成了几呢?各位朋友。这个九变成了,哎哟。是变成六了,同学们。是变成六了,那上面这个变成几的呢?变成九的OK。上面这个是九。好,上面这个是九,我给他改一下这个名字。也就是说经过这样一个调整,是不是你这一方调整,就把你刚才你传进来以I为负极体的这个指数调整的调整成了一个。
26:09
什么队呀,大顶队是不是就变成了四,呃,49856,你看下面他写的应该也是这个49856,看49856是这样的吧,同学们好。只要你理解了,理解了这个代码,各位同学,那下面就一马平川了,其实这里面是最难的,也就这点。最难的一点。好不好,同学们好,那我讲到这儿,下面我相信大部分同学都应该知道怎么写了。好,那么我们来玩一把。
我来说两句