00:00
同学们,我们继续来学习数据结构和算法,那前面呢,我们把数结构给大家做了基本的介绍,包括二叉树,二叉树的便利对吧,二叉树的这一个删除,包括我们的顺序存储二叉树,还有线线线索化二叉树都讲了,那现在呢,我们来看一下树结构的实际应用。这个呢,就是把数结构实际应用到我们的一些这个项目里边,或者说用到一些实际的这个需求里边,那我们来看一下第一个。先看第一个堆排序,堆排序其实就是我们这个数结构的一个应用,那我们来首先呢来看一下何为堆排序,何为堆开堆排序,我们来看一下各位朋友。首先我们看堆排序呢,它是用利用堆这种数据结构而设计的一种排序算法,是不是前面我们已然讲过了八种排序算法,还留了一个叫堆排序,当时我们讲过堆排序呢,它是要以树结构为基础的,因此呢,我们放在这来讲的堆排序呢,它仍然是一种选择排序,它的最坏最好平均复杂度呢,都是一个。
01:14
线性对数阶,而且它也是不稳定的,呃,排序,那不稳定是什么意思,我这里就不解释了啊,那第二点我们要知道,堆是具有以下性质的,一一个完全二叉树,也就是说堆呢,它是一种比较特特殊的二叉树,它要满足什么条件呢?各位同学请看每个节点的值,注意听啊,每个节点的值都大于或者等于其左右孩子节点的值。也就是说,我假如这里有一个节点,这个节点下面呢,有两个子节点,要求负节点的值。要干什么呢?要大于或者是等于它的左右指孩子,呃,左,左右孩子节点的子,那么当这个就称之为大颈椎。
02:03
这样的这样的这种完全二叉树呢,就称之为大顶堆,注意啊,嗯,至于你左右孩子,比如说这是A,这是B,它左右孩子之间的值的大小关系呢,并没有做要求。啊,并没有做要求。呃,第三点我们要说明一下,每个节点的值如果都小于或者等于其左右孩子节点的值,我们称之为小顶,对。啊,那么现在呢,我们来看这个大顶堆,这就是个大顶堆,大家有没有发现。那为什么说这个是一个大顶椎,首先我们看它是一个完全二叉树,对不对,它满足完全二叉树的这种要求,而且有没有发现50它是大于45和40的。也就是说50大于它的左右。孩子的值,那么我们看45 45呢,大于它的,呃,大于他的左右,孩子是20和25。四呃,45啊,这四十四十大于35和30,所以说下面也是一样,20大于十和15,因此这就是个大顶堆,因为它满足大顶堆的一个定义。
03:08
好,那如果说这个大顶堆我们按照这个顺序存储,我们前前面是不是讲过顺序存储我们的二套说如果按照顺序存储的话呢,它的这个存储形式就是50 45,四十二十,25 35,三十十四十五,对不对,按顺序来存就行了,而而且大家有没有注意观察大顶椎的特点是什么?就是说假设这个I是大顶堆的一个节点,在它的顺序存储的数组里面的,呃,这个下标的话,Ii是从零开始编号的啊,那么它应该大于什么呢?它大于它的。左子节点对应的这个值二乘以I加一是不是它对应的左子节点在。数组里面的那个下标。同样,它同时还要满足什么呢?大于它的右子节点,而它的右子节点在数组里面。
04:03
对应的下标是二乘以I加二,所以这个条件是要大于等于,这就是大顶对。这就是大顶推明白。好,嗯,那么紧接着我们来再看一个小顶堆,小顶堆呢跟刚才是不一样的,它是这个节点就是说。它所有节点的,呃,节点的值呢,都小于它的左右子孩子的值,你比如说十,十小于20和15没问题吧,再看。20小于25和40和50是不是也满足,再看15 15小于30和40,我们再看25 25小于35和45,对不对?所以说它满足刚才我们说的那个定义什么呢?就是它的任何一个节点的值都小于它的左右子孩子的子。小顶堆它有个特点是什么呢?就是RI,如果小顶堆按照这个数组顺序存储来说的话呢,它RI应该小于等于二乘以I加一,为什么呢?这个I是这个节点。
05:11
这个节点在存到呃,按顺序存储到数组里面的话,一个下标,那么它对应的左子节点的下标就应该是二乘以I加一,所以说它小于等于,同样它要小于等于它的右子节点在数组里面存储的这个下标对应的那个值。好I仍然是从零开始变好的。那这里我们说到了大顶椎和小顶椎,这个基本概念大家知道了吧,这个一定要清楚啊,待会如果说你不清楚,我在写堆排序的时候,你一脸茫然。第二第六点要说一下,我们如果是使用堆排序,如果我们使用堆排序,那么我们一般是通过通过这个构建大顶堆来完成升序排列,如果我们要对这个数组进行小降序排序,降序排列,而且我们希望想希望用堆排序的话呢,我们是采用小顶堆来实现的。
06:09
各位同学,这个呢,就是给大家讲的大顶堆和小顶堆的概念,大家知道没有,好,那关于大顶堆小顶堆的概念先给大家聊这儿,下面呢,我们一会儿跟大家聊堆排序的一个思想。
我来说两句